[leetcode] Longest Consecutive Sequence | 数组里整数能连起来的最长长度

Posted by: lexigrey on: July 21, 2013

• In: leetcode
• 5 Comments

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.

这个算法挺难想到的。让O(n)说明不能sort，那只能用container。但是用container怎么traverse连续的呢？又不能sort key。所以，我们人眼是怎么做这个题的呢，上来是100，我们其实就想找99和101，有的话就接着那个方向，直到找不着了为止。这样算过的数就从set里删掉，既然是别人的连续，那也是自己的连续，所以不用看了。这样过一遍就能把所有连续数列找全，没有元素重复处理的。

public int longestConsecutive(int[] num) {
    int res = 0;
    Set<Integer> set = new HashSet<Integer>();
    for (int i : num)
        set.add(i);
    for (int i = 0; i < num.length && !set.isEmpty(); i++) {
        int len = 0;
        //go up
        for (int j = num[i] - 1; set.contains(j); j--) {
            set.remove(j);
            len++;
        }
        //go down
        for (int j = num[i]; set.contains(j); j++) {
            set.remove(j);
            len++;
        }
        res = Math.max(res, len);
    }
    return res;
}

Tags: array