【leetcode】128. 最长连续序列

题目内容

128. 最长连续序列

思路分析

本题一上来的考虑是排序然后数一下连续的个数，但做出来以后发现会超时。正确的思路是使用哈希

方法一：排序（超时）

使用快排对数组进行排序，然后数连续的个数。

方法二：哈希

参考资料

内层循环：

将每个数num哈希存储（这里使用C++的unorderd_set，查找的时间复杂度为O(1)），然后不断将num+1，判断+1后的数是否在集合中。

外层循环：

遍历每个数num，但当num-1在集合中时，不进入内循环。这个优化可以去除多余操作，降低时间复杂度。

每个元素只会进入内层循环一次，因此时间复杂度为O(n)。

代码

#include <vector>
#include <iostream>
#include <math.h>
#include <limits.h>
#include <unordered_set>

using namespace std;

// 快排（超时）
// 时间复杂度O(nlogn)
class Solution1 {
public:
    void quickSort(vector<int>& nums) {
        // 快速排序指定数组
        quickSort(nums, 0, nums.size() - 1);
    }
    
    void quickSort(vector<int>& nums, int start, int stop){
        // 快速排序算法实现
        // nums: 要排序的数组
        // start: 开始下标
        // stop: 结束下标
        // 即[start, stop]闭区间

        if (start >= stop) {
            return;
        }
        
        int pivot = nums[start];
        // i的初始值应该是start而非start+1，如果是start+1的话若nums是一个顺序数组，
        // i和j会相遇在下标为1处，而非正确的0处。
        int i = start; 
        int j = stop;
        while (i != j) {
            // 先从右往左找，可以保证i与j在小于标兵区相遇。而标兵选取的是数组的第一个
            // 值，这样可以保证相遇处的值与标兵交换后，该值位于小于标兵区。
            while (i < j && nums[j] >= pivot) {
                --j;
            }

            while (i < j && nums[i] <= pivot) {
                ++i;
            }

            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        nums[start] = nums[i];
        nums[i] = pivot;

        cout << "sort " << start << " to " << stop << endl;
        for (auto num : nums) {
            cout << num << " ";
        }
        cout << endl;

        quickSort(nums, start, i - 1);
        quickSort(nums, i + 1, stop);
    };
    int longestConsecutive(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        
        quickSort(nums);

        int longest_consecutive = 1;
        int consecutive_num = 1;
        int last_num = nums[0];

        for (int i = 1; i <= len - 1; ++i) {
            if (nums[i] == last_num + 1) {
                consecutive_num += 1;
            // 当nums[i] == last_num时，consecutive_num不变
            } else if (nums[i] != last_num) { 
                consecutive_num = 1;
            }

            if (consecutive_num > longest_consecutive) {
                longest_consecutive = consecutive_num;
            }
            last_num = nums[i];
        }

        return longest_consecutive;
    }
};

// 哈希
// 时间复杂度O(n)
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        
        unordered_set<int> nums_set;
        for (auto num : nums) {
            nums_set.insert(num);
        }

        int longest_consecutive{ 1 }, current_consecutive{ 1 };
        for (auto num : nums_set) {
            if (nums_set.find(num - 1) != nums_set.end()) {
                continue;
            }

            int consecutive_num{ num };
            while (1) {
                consecutive_num += 1;
                if (nums_set.find(consecutive_num) != nums_set.end()) {
                    current_consecutive += 1;
                } else {
                    if (current_consecutive > longest_consecutive) {
                        longest_consecutive = current_consecutive;
                    }
                    current_consecutive = 1;
                    break;
                }
            }
        }
        return longest_consecutive;
    }
};

int main() {
    Solution s;
    vector<int> input{ 9,1,-3,2,4,8,3,-1,6,-2,-4,7 };
    // s.quickSort(input, 0, input.size() - 1);
    cout << s.longestConsecutive(input) << endl;
}

扩展知识

快速排序的时间复杂度

最好和平均都是nlogn，可以从树的角度理解，快速排序其实就是不断的将一堆数分为数的两个分支，分的越均匀查起来越快，树深为logn，每层遍历n次。

最坏是n^2，具体的情景有：

顺序数组
倒序数组
数全都一样的数组

这时只往树的一边分支，每次只能分为1个数+其它数，快排弱化为冒泡排，时间复杂度为O(n^2)。

C++的set与unordered_set

set的底层实现是红黑树，可以自动完成排序。

而unordered_set的底层实现是哈希表，它访问单个元素的速度比set快。

收获

复习了遍快排
掌握了下哈希的一个用处
稍微了解了下set和unordered_set