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.
1 public class Solution { 2 public int longestConsecutive(int[] num) { 3 int len = num.length; 4 HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>(); 5 boolean [] visited =new boolean[len]; 6 for(int i=0;i<len;i++){ 7 hm.put(num[i],i); 8 } 9 int res = 0; 10 for(int i=0;i<len;i++){ 11 int count = 1; 12 if(visited[i]) continue; 13 int index = num[i]; 14 while(hm.containsKey(--index)){ 15 count++; 16 visited[hm.get(index)]=true; 17 } 18 index = num[i]; 19 while(hm.containsKey(++index)){ 20 count++; 21 visited[hm.get(index)]=true; 22 } 23 res = Math.max(count,res); 24 } 25 return res; 26 } 27 }