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)---->使用hash，空间换时间

对于当前数N，我们检查N-1, N-2, N-3....N-K是否在hashmap中

对于当前数N，我们检查N+1, N+2, N+3....N+j是否在hashmap中

这里使用visited数组来记录已经访问过的数，这样减少检查次数，时间复杂度O(n)

[Thoughts]
Since it requires O(n) solution, normal sort won't be work here. Hash probably is the best choice.
3 Steps:
1. create the hashmap to hold <num, index>
2. scan the num vector from left to right, for each num
               i, check whether num -1 is in the map  (loop)
              ii, check whether num+1 is in the map  (loop)
3. track the sequence length during scanning.

public class Solution {
    public int longestConsecutive(int[] num) {
        int len = num.length;
        Map<Integer, Integer> map = new HashMap<Integer,Integer>();
        
        for(int i = 0; i< len; i++){
            map.put(num[i],i);
        }
        
        int result = 0, count;
        int[] visited = new int[len];
        
        //这里使用visited数组来记录已经访问过的数，这样减少检查次数，时间复杂度O(n)
        for(int i = 0; i< len; i++){
            count =1 ;
            if(visited[i] == 1){
                continue;
            }
            
            int index = num[i];
            visited[i] = 1;
            
            //注意 --index 先递减
            while(map.containsKey(--index)){
                count++;
                visited[map.get(index)] = 1;
            }
            // index 归位
            index = num[i];
            
            //注意 ++index 先递增
            while(map.containsKey(++index)){
                count++;
                visited[map.get(index)] = 1;
            }
            
            // result 记录之前的最大长度，与每次循环得到的长度相比，取最大
            if(count > result) result = count;
            
        }
        
        return result;
    }
}

ref: http://www.cnblogs.com/feiling/p/3265197.html

http://fisherlei.blogspot.com/2013/02/leetcode-longest-consecutive-sequence.html