算法

每日leetcode-128

  1. 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 *O(n)*。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 `[1, 2, 3, 4]。它的长度为 4。

https://leetcode-cn.com/problems/longest-consecutive-sequence/

简单解答

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        vector<tuple<int, int>> intervals;
        for (auto i = nums.begin(); i != nums.end(); i++) {
            bool ok = false;
            for (auto t = intervals.begin(); t != intervals.end(); t++) {
                if (get<0>(*t) == *i) {
                    ok = true;
                    break;
                }
                if (get<0>(*t) > *i) {
                    bool done_with_first = false;
                    if (t != intervals.begin()) { // 需要检查前一个
                        if (get<1>(*(t - 1)) == (*i) - 1) { // 前一个需要和这个数字合并
                            if (get<0>(*t) == (*i) + 1) { // 前面一个后面一个刚好加上数字合并
                                get<1>(*(t - 1)) = get<1>(*t);
                                intervals.erase(t);
                            } else { // 只把前面的和这个数字合并
                                get<1>(*(t - 1)) = *i;
                            }
                            done_with_first = true;
                        }
                        else if (get<1>(*(t - 1)) >= (*i)) {
                            // 已经有了，不用管了
                            done_with_first = true;
                        }
                    }
                    if (!done_with_first) {
                        // 前面的不用合并，检查后面的
                        if (get<0>(*t) == (*i) + 1) { // 后面一个刚好加上数字合并
                            *t = make_tuple(*i, get<1>(*t));
                        } else {
                            // 需要加上这个数字
                            intervals.insert(t, make_tuple(*i, *i));
                        }
                    }
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                if (intervals.begin() != intervals.end()) {
                    if (get<1>(*(intervals.end() - 1)) == *i - 1) {
                        get<1>(*(intervals.end() - 1)) = *i;
                        continue;
                    }
                    if (get<1>(*(intervals.end() - 1)) > *i - 1) {
                        continue;
                    }
                }
                intervals.emplace_back(*i, *i);
            }
        }
        int ans = 0;
        for (auto t = intervals.begin(); t != intervals.end(); t++) {
            ans = max(get<1>(*t) - get<0>(*t) + 1, ans);
        }
        return ans;
    }
};

里面有几点要注意：

  1. 要注意新的数字和之前的interval的内容可以相连的时候（包括没有比这个数字大，但是可以和最后一个相连的情况）
  2. 要注意可以有重复的数字，比如[0,0,1,-1]

但是这样的话比较慢，如下：

1
2
执行用时 :28 ms, 在所有 C++ 提交中击败了15.55%的用户
内存消耗 :12.2 MB, 在所有 C++ 提交中击败了5.04%的用户

好的解答

官方题解的做法，直接将所有数字加到HashSet里面，对每个数字：

  • 如果比他小1的在这个set里面，就不用找了；
  • 找从它开始连续增加1的序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numbers;
        for (auto i = nums.begin(); i != nums.end(); i++) {
            numbers.insert(*i);
        }
        int ans = 0;
        for (auto i = numbers.begin(); i != numbers.end(); i++) {
            if (numbers.find(*i - 1) != numbers.end()) {
                continue;
            }
            int cur = *i;
            int len = 1;
            while (numbers.find(cur + 1) != numbers.end()) {
                cur++;
                len++;
            }
            ans = max(len, ans);
        }
        return ans;
    }
};