[LeetCode][Java] 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.

题意：

给定一个未排序的整数数组，返回最长的连续元素的长度。

给定[100, 4, 200, 1, 3, 2],

最长连续元素序列为[1, 2, 3, 4].返回它的长度为：4.

你的算法的复杂度应该为O(n) .

算法分析：

   *  排序的话至少要O(nlgn) 的复杂度。

   *  O(n)的复杂度，目前只找到了使用hash来解决的方案，

   *  add, remove, contains 等方法的复杂度都是 O(1)，因此两次遍历的操作复杂度为 O(n)。

    *  先把数字放到一个集合中，拿到一个数字，就往其两边搜索，得到包含这个数字的最长串，

    *  并且把用过的数字从集合中移除（因为连续的关系，一个数字不会出现在两个串中）。最后比较当前串是不是比当前最大串要长，是则更新。

    * 如此继续直到集合为空。

    *  After an element is checked, it should be removed from the set.

    *  Otherwise, time complexity would be O(mn) in which m is the average length of all consecutive sequences.

AC代码：

<span style="font-size:12px;">public static int longestConsecutive(int[] num) 
    {
    	// if array is empty, return 0
    	if (num.length == 0) 
    		return 0;
    		
    	Set<Integer> set = new HashSet<Integer>();
    	int max = 1;
     
    	for (int e : num)
    		set.add(e);
     
    	for (int e : num) 
    	{
    		int left = e - 1;
    		int right = e + 1;
    		int count = 1;
     
    		while (set.contains(left)) 
    		{
    			count++;
    			set.remove(left);
    			left--;
    		}
     
    		while (set.contains(right)) 
    		{
    			count++;
    			set.remove(right);
    			right++;
    		}
     
    		max = Math.max(count, max);
    	}
    	return max;
    }
}</span>

[LeetCode][Java] Longest Consecutive Sequence

原文：http://blog.csdn.net/evan123mg/article/details/47130489