Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Have you met this question in a real interview? 

Yes

Clarification

Your algorithm should run in O(n) complexity.

Example

Given [100, 4, 200, 1, 3, 2],The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length: 4.

 

LeetCode上的原题，请参见我之前的博客Longest Consecutive Sequence。

 

解法一：

class Solution {

public:

/**

* @param nums: A list of integers

* @return an integer

*/

int longestConsecutive(vector &num) {

int res = 0;

unordered_set s(num.begin(), num.end());

for (int d : num) {

if (!s.count(d)) continue;

s.erase(d);

int pre = d - 1, next = d + 1;

while (s.count(pre)) s.erase(pre--);

while (s.count(next)) s.erase(next++);

res = max(res, next - pre - 1);

}

return res;

}

};

 

解法二：

class Solution {

public:

/**

* @param nums: A list of integers

* @return an integer

*/

int longestConsecutive(vector &num) {

int res = 0;

unordered_map m;

for (int d : num) {

if (m.count(d)) continue;

int left = m.count(d - 1) ? m[d - 1] : 0;

int right = m.count(d + 1) ? m[d + 1] : 0;

int sum = left + right + 1;

m[d] = sum;

res = max(res, sum);

m[d - left] = sum;

m[d + right] = sum;

}

return res;

}

};

 

查看原文