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、直接用排序。。当然不行了，时间复杂度超过了O(n)，虽然AC了。
public class Solution {
public int longestConsecutive(int[] nums) {
int result = 1;
if( nums.length == 0)
return result;
Arrays.sort(nums);
for( int i = 1;i<nums.length;i++){
int a = 1;
while( i<nums.length && (nums[i] == nums[i-1]+1 || nums[i] == nums[i-1]) ){
if( nums[i] == nums[i-1]+1 )
a++;
i++;
}
result = Math.max(a,result);
}
return result;
}
}
2、用set集合。遍历两次，得出结果，由于add，remove，contains都是O(1)的复杂度，所以时间复杂度符合题意。
public class Solution {
public int longestConsecutive(int[] nums) {
if( nums.length == 0)
return 0;
Set set = new HashSet<Integer>();
for( int num : nums)
set.add(num);
int result = 1;
for( int e : nums){
int left = e-1;
int right = e+1;
int count = 1;
while( set.contains(left )){
set.remove(left);
count++;
left--;
}
while( set.contains(right) ){
set.remove(right);
count++;
right++;
}
result = Math.max(result,count);
}
return result;
}
}