跳转至

128 最长连续序列

暴力做法

根据题意首先要对数组进行去重,去重可采用set/unordered_set/map/unordered_map等容器

最简单的思路:

  • 遍历每个元素x,不断在数组中找出值为x, x + 1, x +2, ... , x + y的元素,计算长度 y + 1
  • 既能满足去重又能快速找出值的数据结构且不要求值有序,使用unordered_set即可
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 去重
        unordered_set<int> nums_set;
        for(auto num : nums){
            nums_set.insert(num);
        }
        int n = nums_set.size();
        int maxLen = 0;
        for (auto num : nums_set) {
            int curNum = num;
            int curLen = 0;
            while(nums_set.count(curNum)){
                curNum++;
                curLen++;
            }
            maxLen = max(maxLen,curLen);
        }
        return maxLen;
    }
};

时间复杂度:\(O(n^2)\)

  • 对于每个元素都遍历了curLen次

空间复杂度:\(O(n)\)

优化版

暴力解法的缺点在于会重复寻找数字连续的最长序列:

比如说

  • 当前元素是x,按暴力解法的做法,我们会遍历x, x + 1, x +2, ... , x + y的元素,计算长度 y + 1
  • 如果当前元素是x + 1,按暴力解法的做法,我们会遍历x + 1, x +2, ... , x + y的元素,计算长度 y
  • ...
  • 如果当前元素是x + y - 1,按暴力解法的做法,我们会遍历x + y - 1, x + y的元素,计算长度 2
  • 如果当前元素是x + y,按暴力解法的做法,我们会遍历x + y的元素,计算长度 1

如何避免这种情况呢

我们发现:如果当前元素是x + 1,那么x + 1遍历的元素, x已经遍历过了;推广到x + k, x + k遍历的元素, x + k - 1也遍历过了

那么我们只需要寻找当前元素的前置元素是否存在,就可以判断该序列是否已经遍历过了

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 去重
        unordered_set<int> nums_set;
        for(auto num : nums){
            nums_set.insert(num);
        }
        int n = nums_set.size();
        int maxLen = 0;
        for (auto num : nums_set) {
            int curNum = num;
            int curLen = 0;
            // 与暴力解法相比,加了这一行代码,其他都不变
            if(nums_set.count(num - 1))
                continue;
            while(nums_set.count(curNum)){
                curNum++;
                curLen++;
            }
            maxLen = max(maxLen,curLen);
        }
        return maxLen;
    }
};

时间复杂度:\(O(n)\)

  • 看起来是时间复杂度是\(O(n^2)\),实际上,假设数字连续的最长序列的长度为maxLen,数组去重后长度为n,我们遍历n - maxLen个不在数字连续的最长序列的元素,由于我们的优化操作,我们只从最终数字连续的最长序列的第一个元素开始遍历,并且只遍历这个序列一次,因此再遍历maxLen个元素,最终遍历了n个元素,即\(O(n)\)

空间复杂度:\(O(n)\)