LintCode 124 Longest Consecutive Sequence (unordered_set的应用)

124 · Longest Consecutive Sequence
Description
Given an unsorted array num of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

10000
len(num)<=10000
Example
Example 1:

Input:

num = [100, 4, 200, 1, 3, 2]
Output:

4
Explanation:

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

解法1：用unordered_set。
用bitmap之类的都不行，因为输入的integer范围很大。

class Solution {
public:
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    int longestConsecutive(vector<int> &num) {
        unordered_set<int> s;
        for (auto n : num) {
            s.insert(n);
        }
        int maxLen = 0;
        for (int i = 0; i < num.size(); i++) {
            int lenUp = 0, lenDown = 0;
            if (s.find(num[i]) != s.end()) {
                int tmpUp = num[i] + 1;
                while (s.find(tmpUp) != s.end()) {
                    lenUp++;
                    s.erase(tmpUp);
                    tmpUp++;
                }
                int tmpDown = num[i] - 1;
                while (s.find(tmpDown) != s.end()) {
                    lenDown++;
                    s.erase(tmpDown);
                    tmpDown--;
                }
                maxLen = max(maxLen, lenUp + lenDown + 1);
            }
        }
        return maxLen;
    }
};
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