未排序寻找连续 leetcode -- Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

 

这个方法是先把所有都放进一个set. 找到一个后把它所有附近的都删掉.得到个长度.
这个问题是无法应对动态增长的情况.
public class Solution {
    public int longestConsecutive(int[] num) {

        Set<Integer> set = new HashSet<Integer>();
        
        for (int i : num) {
            set.add(i);
        }
        int max = 0;
        
        for(int i=0; i<num.length; i++){
            if(set.contains(num[i])){
                int next = num[i] - 1;        // 找比num[i]小一个的值
                int count = 1;
                set.remove(num[i]);            // 及时的移除，减少之后的查找时间
                while(set.contains(next)){
                    set.remove(next);
                    next--;
                    count++;
                }
                next = num[i] + 1;        // 找比num[i]大一个的值
                while(set.contains(next)){
                    set.remove(next);
                    next++;
                    count++;
                }
                max = Math.max(max, count);
            }
        }
        
        return max;
    }



}

 

 

 

 

一个小技巧：涉及到O(n)时间，并且还是unordered的东西，可以考虑一下Hash。

对于本题而言，如果是O(n*logn)的时间，还是很好做的——先排序，然后检查。那么，能否用O(n)的时间来做呢？

我们可以用一个HashTable来将所有的数据存储起来。关键问题是，我们如何用O(1)时间来判断连续性？或者说，对于n个元素，查找连续序列的时间能否也是O(n)？从某个元素开始递增寻找？那时间又成了O(n*n)。

这里有一个不太容易想到的思路，那就是：从当前元素递减寻找，从当前元素+1递增寻找，这样一次就能够把连续序列找全。找全后，别忘记清空元素，保证下次不会重复寻找，以减少重复搜寻的次数。

以后涉及到“在未排序集合中寻找有序集合”的题目，可以考虑本题的思路！

 

纸上走一遍基本都能搞定.

不同于上面的题，这个是连接，就像曹操的铁索连环一样。连起来，计算总长度放到value里面。

public int findLongestConsequence(int[] a) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int max = 1;
    for (int i : a) {
        if (map.containsKey(i)) continue;
        map.put(i, 1);
        if (map.containsKey(i - 1)) {
            max = Math.max(max, merge(map, i-1, i));
        }
        if (map.containsKey(i + 1)) {
            max = Math.max(max, merge(map, i, i+1));
        }
    }
    return max;
}

private int merge(HashMap<Integer, Integer> map, int left, int right) {
    int upper = right + map.get(right) - 1;
    int lower = left - map.get(left) + 1;
    int len = upper - lower + 1;
    map.put(upper, len);
    map.put(lower, len);
    return len;
}