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.
Analysis:
We use hash table to store each element. For element, we search the value smaller and larger than it in the table and find out the current max len. We mark every visited element.
Solution:
1 public class Solution { 2 public int longestConsecutive(int[] num) { 3 if (num.length==0 || num.length==1) return num.length; 4 5 Map<Integer,Boolean> map = new HashMap<Integer,Boolean>(); 6 for (int i=0;i<num.length;i++) 7 map.put(num[i],false); 8 9 int maxLen = 0; 10 for (int i=0;i<num.length;i++){ 11 int curVal = num[i]; 12 if (map.get(curVal)) continue; 13 14 int curLen = 1; 15 map.put(curVal,true); 16 int val = curVal-1; 17 while (map.containsKey(val) && !map.get(val)){ 18 curLen++; 19 map.put(val,true); 20 val--; 21 } 22 val = curVal+1; 23 while (map.containsKey(val) && !map.get(val)){ 24 curLen++; 25 map.put(val,true); 26 val++; 27 } 28 if (maxLen<curLen) maxLen = curLen; 29 } 30 31 return maxLen; 32 } 33 }
Leetcode-Longest Consecutive Sequence
原文：http://www.cnblogs.com/lishiblog/p/4117771.html