Description:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
My Accept solution:
Sorting O(nlgn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
var longestConsecutive = function(nums) {
if(nums.length < 2) return nums.length;
nums = nums.sort(numsort);
let max = 0,
temp = 1;
for(let i = nums.length-1; i > 0; i--){
if(nums[i] === nums[i-1]){
max = Math.max(temp, max);
continue;
}else if(nums[i] - 1 == nums[i-1]){
temp++;
}else{
temp = 1;
}
max = Math.max(temp, max);
}
return max ;
};
var numsort = (a, b) => {
return a-b;
}
|
Hash-set O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var longestConsecutive = function(nums) {
if(nums.length < 2) return nums.length;
let max = 0;
nums.forEach(num => {
if(!nums.includes(num-1)){
let curNum = num;
let temp = 1;
while(nums.includes(curNum+1))
{temp++;
curNum++}
max = Math.max(max, temp);
}
})
return max ;
};
|
When the nums is very long, hash-set solution is a drain on memory, and when it is small, there is no big difference with sorting solution.