LeetCode笔记（8）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.

看到O(n)，这一题的思路很直接的就到了hashmap。最暴力的方法：从最小值一个个加到最大值，记录当前连续长度，然后找出最大的。但是这是O(W)的， W = max – min。如果W很大，效率也会很低，顶多算是个pseudo-linear.

在网上看看帖之后发现，其实离争取思路不是很远了：如果换做从每个数列中的数字上下找，那么复杂度就是O(n)了。使用unordered_map，每个数字分为三种状态：不在数组中，则hashmap中没有这个key；在数组中但是没访问：有key，value设置为 false；在数组中且已经访问：有key，设置为true。代码如下:

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, bool> visited;
        for (int i=0; i<num.size(); i++)
            visited[num[i]] = false;

        int max = 0;
        for (int i=0; i<num.size(); i++)
        {
            if (visited[num[i]])
                continue;
            visited[num[i]] = true;

            int h = num[i] + 1;
            while(visited.find(h) != visited.end())
                visited[h++] = true;

            int l = num[i] - 1;
            while(visited.find(l) != visited.end())
                visited[l--] = true;

            int count = h - l - 1;
            if (count > max)
                max = count;
        }
        return max;
    }
};

由于每个element最多被访问两次（直接访问一次，通过+1， -1 访问一次），时间复杂度O(n)

如果不想使用三种状态，则需要利用c++对于bool的默认值：false。对于不存在数组内的值，map[x] 会自动设置为false。那么我们需要将最开始存在的数字设置为true，访问后设置为false。对于false的不再增长计算长度。代码如下：

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, bool> inSeq;
        for (int i=0; i<num.size(); i++)
            inSeq[num[i]] = true;

        int max = 0;
        for (int i=0; i<num.size(); i++)
        {
            if (!inSeq[num[i]])
                continue;
            inSeq[num[i]] = false;

            int h = num[i] + 1;
            while(inSeq[h])
                inSeq[h++] = false;

            int l = num[i] - 1;
            while(inSeq[l])
                inSeq[l--] = false;

            int count = h - l - 1;
            if (count > max)
                max = count;
        }
        return max;
    }
};

最后是一个cluster merge的算法，从这里看到。惊呼高端

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;
}

思路是在每个点都标记自己的范围，然后检查左右neighbour的范围，看能否合并。按任意顺序访问所有元素后，最终总能将连续的范围合并为一个。有空了拿C++实现一下。