128. Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
- new solution update 2022.02.25
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
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> range;
unordered_map<int, unordered_map<int,int>::iterator> endOfRange;
unordered_set<int> dup;
int res = 0;
for(auto n : nums) {
if(dup.count(n)) continue;
dup.insert(n);
auto start = range.find(n + 1);
if(start != range.end()) {
auto newStart = range.insert({n, start->second}).first;
endOfRange[start->second] = newStart;
range.erase(start);
res = max(res, newStart->second - newStart->first + 1);
start = newStart;
} else {
start = range.insert({n,n}).first;
endOfRange[n] = start;
res = max(res, 1);
}
auto fin = endOfRange.find(n - 1);
if(fin != endOfRange.end()) {
auto prevStart = fin->second;
prevStart->second = start->second;
res = max(res, prevStart->second - prevStart->first + 1);
endOfRange[start->second] = prevStart;
range.erase(start);
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()) return 0;
set<int> s(begin(nums), end(nums));
auto i = begin(s);
int res(0), target(*i), cur(0);
while (i != end(s)) {
while(i != end(s) && *i == target) {
cur++;
i++;
target++;
}
res = max(cur, res);
if(i != end(s)) target = *i;
cur = 0;
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()) return 0;
unordered_set<int> s(begin(nums), end(nums));
int res(0), sz(nums.size());
for(int i = 0; i < sz && s.size(); i++) {
if(!s.count(nums[i])) continue;
int cur(1), t(nums[i] + 1), _t(nums[i] - 1);
s.erase(nums[i]);
while(s.count(t)) s.erase(t++), cur++;
while(s.count(_t)) s.erase(_t--), cur++;
res = max(res, cur);
}
return res;
}
};
|
