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