For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
/**
* o(n)复杂度
* @param arrays
* @return
*/
// [100, 4, 200, 1, 3, 2]--> 1,2,3,4 return 4
public static int longestConsecutive(int[] arrays){
final HashSet<Integer> mySet=new HashSet<>();
for (int i:arrays){
mySet.add(i);
}
int longest=0;
for (int value:arrays){
int length=1;
for (int i=value-1;mySet.contains(i);--i){
mySet.remove(i);
++length;
}
for (int i=value+1;mySet.contains(i);++i){
mySet.remove(i);
++length;
}
longest=Math.max(longest,length);
}
return longest;
}
网友评论