128. 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.

方法一：union find 需要每次union的时候记录root下的node数
方法二：最长连续，对于nums[i] 而言看它的前一个数以及后一个数
如果用hashMap记录Range，那么nums[i]要知道nums[i]-1是不是key，如果是key，更新对应value（如果value小于nums[i]）。nums[i]+1是不是value，如果是value，对应key是什么？
如果用 hashMap 记录<num, count> 那么对于每个数都会放入map，找前一个数和后一个数，count = 1 + map.get(num-1) +  map.get(num+1)。需要注意的是在map没有这个数的时候计算，如果是重复数字就跳过。于此同时也要更新map.get(num-1) 以及map.get(num+1)

 public int longestConsecutive(int[] num) {  
   int res = 0;  
   HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  
   for (int n : num) {  
     if (!map.containsKey(n)) {  
       int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;  
       int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;  
       // sum: length of the sequence n is in  
       int sum = left + right + 1;  
       map.put(n, sum);  
       // keep track of the max length   
       res = Math.max(res, sum);  
       // extend the length to the boundary(s)  
       // of the sequence  
       // will do nothing if n has no neighbors  
       map.put(n - left, sum);  
       map.put(n + right, sum);  
     }  
     else {  
       // duplicates  
       continue;  
     }  
   }  
   return res;  
 }  

Union Find 主程序部分

 public int longestConsecutive(int[] nums) {  
     if(nums.length==0) return 0;  
     uf = new int[nums.length];  
     rank = new int[nums.length];  
     count = new int[nums.length];  
     Arrays.fill(count,1);  
     HashMap<Integer,Integer> numToIdx = new HashMap<>();  
     for(int i = 0; i < nums.length; i++){  
       uf[i] = i;  
       numToIdx.putIfAbsent(nums[i],i);  
     }  
     for(int num: nums){  
       if(num!=Integer.MAX_VALUE){  
         if(numToIdx.containsKey(num+1))  
           union(numToIdx.get(num),numToIdx.get(num+1));  
       }  
        if(num!=Integer.MIN_VALUE){  
         if(numToIdx.containsKey(num-1))  
           union(numToIdx.get(num),numToIdx.get(num-1));  
       }  
     }  
     System.out.println(Arrays.toString(uf));  
     return longest;  
   }