【C++】算法与数据结构--最长连续串

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution1 {
    public:
        int longestConsecutive(vector<int>& nums) {
            // 看样子可以实现，但时间不行，有点慢
            // step1 先把nums中的元素放入set中
            unordered_set<int> num_set;
            for (const int& num: nums){
                num_set.insert(num); //这里为什么呢？给我的感觉是重新排序了，其实是弄出来一个set
            }
            int longestStreak = 0; // 然后遍历这个set，找出最长的连续序列
            // step2 遍历set中的元素，找出最长的连续序列
            for (const int& num: num_set)
            {
                int currentNum = num;
                int currentStreak = 1;
                while (num_set.count(currentNum + 1)) // 这里还是很精妙的，之用currentStreak来记录当前连续序列的长度
                {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = max(longestStreak, currentStreak);
            }
            return longestStreak;
        }
};  

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for (const int& num : nums) {
            num_set.insert(num);
        }

        int longestStreak = 0;

        for (const int& num : num_set) {
            if (!num_set.count(num - 1)) { // 前面没有，说明是新的连续序列的开始，向前追溯能够节省大量的重复，太赞了！
                int currentNum = num; 
                int currentStreak = 1;

                while (num_set.count(currentNum + 1)) { // 看下后面是不是能够接上
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = max(longestStreak, currentStreak); // 选择一个最长的串
            }
        }

        return longestStreak;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {100, 4, 200, 1, 3, 2, 9, 10, 11, 12, 13, 14, 101,102,103,104,105,106};
    cout << s.longestConsecutive(nums) << endl;
    return 0;
}

这里面用两个方法解决了这个问题，但是第一个方法不太好，时间复杂度高，在真正跑力扣的时候有一个用例会超时，这是因为
当遇到【1，2，3，4，5，7，8，9】
的时候， s1 会 1—>5, 2–>5, 3–>5, 4–>5, 5, 这样子都跑
而s2 仅仅会跑 1—>5 2–> 1 发现在集合里就jump了 同理3–>2, 4–>3 … 太赞了！！！

原文地址：https://blog.csdn.net/weixin_40293999/article/details/143660248

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！