Leetcode - Longest Consecutive Sequence

Screenshot from 2016-01-13 14:35:58.png

My code:

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        HashSet<Integer> helper = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++)
            helper.add(nums[i]);
        int len = 1;
        int longestLen = 1;
        for (int i = 0; i < nums.length; i++) {
            int tmp = nums[i];
            if (!helper.contains(tmp))
                continue;
            while (helper.contains(tmp - 1)) {
                helper.remove(tmp - 1);
                len++;
                tmp--;
            }
            tmp = nums[i];
            while (helper.contains(tmp + 1)) {
                helper.remove(tmp + 1);
                len++;
                tmp++;
            }
            helper.remove(nums[i]);
            longestLen = Math.max(longestLen, len);
            len = 1;
        }
        return longestLen;
    }
}

看了提示思路之后才写出来。好奇怪，为什么自己想就想不出来！
就是一个左右不断合并的过程。然后不断把已经探明过的值从HashSet中删除以避免重复探测。
参考网址：
http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/

然后还有一种 Union Find 的做法。
我看了网上对该算法的解释和Discuss里面的代码后自己重写了一个，

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        Union union = new Union(nums.length);
        HashMap<Integer, Integer> helper = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (helper.containsKey(nums[i])) {
                continue;
            }
            helper.put(nums[i], i);
            if (helper.containsKey(nums[i] - 1))
                union.union(i, helper.get(nums[i] - 1));
            if (helper.containsKey(nums[i] + 1))
                union.union(i, helper.get(nums[i] + 1));
        }
        return union.maxUnion();
    }
    
    private class Union {
        int[] unions;
        int[] size;
        int count;
        Union(int n) {
            unions = new int[n];
            size = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                unions[i] = i;
                size[i] = 1;
            }
        }
        
        /** return the group id of this index */
        int find(int p) {
            if (p >= unions.length)
                return -1;
            while (p != unions[p])
                p = unions[p];
            return p;
        }
        
        /** test whether two indexs are connectted */
        boolean connected(int p, int q) {
            p = find(p);
            q = find(q);
            return p == q;
        }
        
        /** connect two components by making their group id equal */
        void union(int p, int q) {
            p = find(p);
            q = find(q);
            if (size[p] > size[q]) {
                size[p] += size[q];
                unions[q] = p;
            }
            else {
                size[q] += size[p];
                unions[p] = q;
            }
            count--;
        }
        
        /** return the maximum size of components */
        int maxUnion() {
            int max = 1;
            for (int i = 0; i < unions.length; i++) {
                max = Math.max(max, size[i]);
            }
            return max;
        }
    }
}

然后是Discuss里面的代码：
https://leetcode.com/discuss/68905/my-java-solution-using-unionfound

我比他更快的原因在于，我提前做了一个size数组专门用来记录大小，并且当合并树的时候可以使该算法更快。

Union Find 是普林斯顿算法第一章讲的东西，当时理解起来还有些困难。现在思考下，觉得这个算法的确不错。它解决了什么问题？
当我们需要根据value将index连接起来，而index又相邻时，
Union Find 用代码解决了这个 ** 连接结点 ** 的问题。
Nice Algorithm!
一个比较全面的算法讲解：
http://blog.csdn.net/dm_vincent/article/details/7655764

Anyway, Good luck, Richardo!