128. Longest Consecutive Sequence (Facebook Hard)

题目：

给定顺序的证书数组，返回最长连续元素序列的长度。

举例:给定[100，4，200，1，3，2]，最长的连续元素序列是[1，2，3，4]，

返回:4。

题解：

1. Set 解法

使用集合 set 存所有的数字，然后遍历数组中的每个数字。找到连续序列的左端点和右端点 next。即 pre-1 不在集合中，则令 next=pre+1。那么 next-pre 就是当前数字的最长连续序列，更新max res 即可。需要 O(n)，然后我们可以在 O(1)中查找是否有我们需要的数字。

Running time: O(n)

Space: O(n)

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        //先将所有数字加数组中
        for(int pre : nums){
            set.add(pre);
        }

int res = 0;

for(int pre : nums) {
            //找到连续序列的左端点，即 pre-1 不在集合中 
            //如果数字 n 是条纹的开始(即，n-1 不在该组中)，
            //则测试 m = n + 1，n + 2，n + 3，...并停在第一个数字 m 处在集合中，res 就是 m-n
            if(!set.contains(pre - 1)) {
                int next = pre + 1;
                while(set.contains(next)) {
                    //只要 next 存在在 set 中，向后继续寻找下一个连续的元素
                    next++;
                }
                //那么 next-pre 就是当前数字的最长连续序列，更新 res 即可
                res = Math.max(res, next - pre);
            }
        }

return res;
    }
}

2. Union Find 解法

使用两个array, 一个number[]存union-find的parent index，另一个number2[]存root对应的最大长度。

Running time: O(n)

Space: O(n)

这是因为路径压缩函数 exhibits growth which follows the Inverse Ackermann Function From Princeton Algorithm1.

public class Solution {

int[] number;
    int[] number2;
    Map<Integer, Integer> map;

public int longestConsecutive(int[] nums) {
        number = new int[nums.length];
        number2 = new int[nums.length];
        map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            insert(nums[i], i);
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(res, number2[i]);
        }
        return res;
    }

void insert(int num, int index) {
        if (!map.containsKey(num)) {
            map.put(num, index);
            number[index] = index;
            number2[index] = 1;
            if (map.containsKey(num - 1)) {
                unite(num - 1, num);
            }
            if (map.containsKey(num + 1)) {
                unite(num + 1, num);
            }
        }
    }

void unite(int exp1, int exp2) {
        int pre = findSet(map.get(exp1));
        int curr = findSet(map.get(exp2));
        if (pre != curr) {
            if (number2[pre] > number2[curr]) {
                number[curr] = pre;
                number2[pre] += number2[curr];
            } else {
                number[pre] = curr;
                number2[curr] += number2[pre];
            }
        }
    }

private int findSet(int num) {
        if (number[num] != num) {
            number[num] = findSet(number[num]);
        }
        return number[num];
    }
}

会比使用set快2ms.