-
Notifications
You must be signed in to change notification settings - Fork 8
/
longest-consecutive-sequence.cpp
44 lines (40 loc) · 1.06 KB
/
longest-consecutive-sequence.cpp
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
40
41
42
43
// Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
//
// Your algorithm should run in O(n) complexity.
//
// 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.
//
//
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> set(nums.begin(), nums.end());
int ans = 0;
int current = 0;
while (!set.empty()) {
int x = (*set.begin());
current += 1;
set.erase(x);
int temp = x-1;
while (set.find(temp) != set.end()) {
++current;
set.erase(temp);
--temp;
}
temp = x+1;
while (set.find(temp) != set.end()) {
++current;
set.erase(temp);
++temp;
}
ans = std::max(ans, current);
current = 0;
}
return ans;
}
};