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.
思考：空间换时间，查找O(1)用unordered_set。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 |
class
Solution {public: int
longestConsecutive(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function unordered_set<int> existTable; for(int
i = 0; i < num.size(); ++i) existTable.insert(num[i]); unordered_set<int> visitedTable; int
mmax = INT_MIN; for(int
i = 0; i < num.size(); ++i) { int
curNum = num[i]; if(visitedTable.find(curNum) != visitedTable.end()) continue; int
cnt = 1; //search left int
left = curNum; while(existTable.find(--left) != existTable.end()) cnt++, visitedTable.insert(left); int
right = curNum; while(existTable.find(++right) != existTable.end()) cnt++, visitedTable.insert(right); mmax = max(cnt, mmax); } return
mmax; }}; |
[LeetCode]Longest Consecutive Sequence,布布扣,bubuko.com
[LeetCode]Longest Consecutive Sequence
原文：http://www.cnblogs.com/Rosanna/p/3597902.html