Longest Consecutive Sequence

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.

Naive Way:O(n)应有两种方案，一种是用hashmap，一种是用bucket sort的思想。想了一想bucket sort，可以将数字全部分割成小组，然后再每个小组内再分割，直到某个小组容量正好等于数的数量就是连续的，但是还要追溯相邻的小组，反正不太像O(n)的。如果用hashmap，好像好做一点，可以map相邻的两个数，记下起点，最后不停追溯map，但是每次记录起点又需要O(n)的追溯了。还可以map连续出现的个数，比如一开始100->1, 4->1, 200->1，然后3出现，就要使得3->2, 4->2，这样有个麻烦就是如果已匹配好的连续数段很长，还要每一个更新一遍映射。后来仔细想了想，不用所有的都更新，只需要更新一头一尾。

算法复杂度O(n)， space O(n)。

 

 public class Solution {  
   public int longestConsecutive(int[] num) {  
     int longest = 0;  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     for(int i = 0;i < num.length;i++){  
       // if there is no duplicates, these two lines can be commented  
       if(map.containsKey(num[i])) continue;  
       map.put(num[i],1);  
       int end = num[i];  
       int begin = num[i];  
       if(map.containsKey(num[i]+1))  
         end = num[i] + map.get(num[i]+1);  
       if(map.containsKey(num[i]-1))  
         begin = num[i] - map.get(num[i]-1);  
       longest = Math.max(longest, end-begin+1);  
       map.put(end, end-begin+1);  
       map.put(begin, end-begin+1);  
     }  
     return longest;  
   }  
 }