Leetcode 128.最长连续序列

题目描述：

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

示例 1：

1
2
3

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• $0 <= nums.length <= 10^4$
• $-10^9 <= nums[i] <= 10^9$

链接：

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

题目分析

1.Set

  阅读示例后发现，题目所说的连续序列只需要数字的值连续，而不需要在数组中相对有序，更不需要连续出现，则某个数在数组中只有 “存在” 与 “不存在” 两种状态，它的个数、位置都是没有影响的，我们可以考虑使用一个 set 容器来存放这些数，这样在存放的时候就可以同时进行排序。
  存放所有的数后，我们只需要对 set 进行一次遍历，每次寻找数字的值是否连续，并维护一个 count 进行计数，一旦不连续则重置，寻找下一个连续序列，与此同时记录最大的序列长度即可。代码中的 result 用于存放最大序列长度（也即结果），count 用于序列长度计数，pre 用于存放遍历的上一个值（用于比较）。重置的时候是重置为 1 （也即已经算上当前的这个数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        set<int> number;
        for(auto num : nums){
            number.insert(num);
        }
        int result = 1, count = 1, pre = INT_MIN;
        for(auto it : number){
            if(it == pre + 1){
                count++;
                result = max(result, count);
            }
            else{
                count = 1;
            }
            pre = it;
        }
        return result;
    }
};

  时间复杂度：$O(n\log n)$，其中 $n$ 为数组的大小。我们遍历了一次数组存入 set 容器中，每一个数的存入需要 $O(\log n)$，再遍历一次 set 找到答案。
  时间复杂度：$O(n)$，其中 $n$ 为数组的大小。我们需要一个 set 容器来存放数组中出现的所有数字，最大的大小为 $n$。

  PS：进阶要求的时间复杂度是 $O(n)$，但是我看了官方题解仍然觉得是 $O(n\log n)$，并没有更好的算法了吧。看了官方题解的评论，大概是说最优情况下是 $O(n)$，那倒确实。
  PPS：所以好像直接对原数组排序一遍再遍历更省事更快，还不需要那么多的额外空间…
  PPPS：发生了非常魔幻的事情，8月4日的这一天重新看这道题，发现官方题解和我之前看的不一样了，但是又是发布于2020年的题解，就好像做梦一样。这道题确实是存在 $O(n)$ 的解法的。

2.哈希表

  如果我们使用哈希表来存储这些数字，然后再遍历哈希表进行查找，每次查找的时候，如果这个数是连续序列的第一个数（也即其减一不存在于哈希表中），我们就查找这个连续序列的长度。而查找哈希表中是否存在某个数的复杂度是 $O(1)$，则我们遍历的时间复杂度为 $O(n)$。如此遍历完哈希表就可以获得所有的连续序列长度了。当然，我们只需要记录下最长的那个长度。

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) {
        if(nums.size() == 0) return 0;
        unordered_set<int> number;
        for(auto num : nums){
            number.insert(num);
        }
        int result = 0;
        for(auto num : number){
            if(!number.count(num-1)){
                int curnum = num;
                int curlen = 0;
                while(number.count(curnum)){
                    curnum++;
                    curlen++;
                }
                result = max(result, curlen);
            }
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为数组的大小。我们遍历了一次数组存入哈希表中，所需时间复杂度为 $O(n)$。然后哈希表中的每个数字被遍历两次，一次为外层遍历时，一次是作为连续序列中的一个数被遍历一次（每个连续序列只会在第一个数进入内循环时被遍历，有且仅有一次），因此时间复杂度也是 $O(n)$。
  时间复杂度：$O(n)$，其中 $n$ 为数组的大小。我们需要一个哈希表来存放数组中出现的所有数字，最大的大小为 $n$。