## leetcode——Longest Consecutive Sequence

2018年04月12日 ⁄ 综合 ⁄ 共 1345字 ⁄ 字号 评论关闭

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.

AC代码：

public class Longest_Consecutive_Sequence {
public int longestConsecutive(int[] num) {
HashMap<Integer,Boolean> map = new HashMap<Integer, Boolean>(num.length);
for(int i=0;i<num.length;i++){
map.put(num[i],false);
}
int max = 0;
for(int i=0;i<num.length;i++){
int len = 0;
if(!map.get(num[i])){
len++;
map.put(num[i],true);
int j = num[i]-1;
while(map.containsKey(j) && !map.get(j)){
len++;
map.put(j,true);
j--;

}

j = num[i]+1;
while(map.containsKey(j) && !map.get(j)){
len++;
map.put(j,true);
j++;
}
max = max>len?max:len;
}
}
return max;
}
public static void main(String[] args){
Longest_Consecutive_Sequence longest_consecutive_sequence = new Longest_Consecutive_Sequence();
int[] num = {100,4,200,1,3,2};
System.out.println(longest_consecutive_sequence.longestConsecutive(num));
}
}