题目:
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,
. Return its length:
2, 3, 4]4
.
Your algorithm should run in O(n) complexity.
思路:
利用一个哈希表存储出现的数据,利用另一个哈希表保存访问过的数据。遍历每个数据,若未访问时,向上向下进行遍历,确定最大连续长度。
代码:
class Solution { public: int longestConsecutive(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function map<int, int> hashtable; map<int, int> visited; int max = 0; for(int i = 0; i < num.size(); i++) { hashtable[num[i]] = 1; } for(int i = 0; i < num.size(); i++) { if(visited[num[i]] == 1) { continue; } bool up = true, down = true; int up_cur = num[i], down_cur = num[i]; int up_len = 0, down_len = 0; while(up || down) { if(up) { up_cur++; if(hashtable[up_cur] == 1) { visited[up_cur] = 1; up_len++; } else { up = false; } } if(down) { down_cur--; if(hashtable[down_cur] == 1) { visited[down_cur] = 1; down_len++; } else { down = false; } } } if(up_len + down_len + 1 > max) { max = up_len + down_len + 1; } } return max; } };