[Leetcode]--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.

[Leetcode]--Longest Consecutive Sequence
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;
    }
}
[Leetcode]--Longest Consecutive Sequence

 

 

 

 

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

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

[Leetcode]--Longest Consecutive Sequence

上一篇:[Leetcode]-- Reverse Integer


下一篇:libmysqld,嵌入式MySQL服务器库