原题链接： Leetcode 128. 最长连续序列
解法1: map，不符合要求
class Solution {
public:int longestConsecutive(vector<int>& nums) {if (nums.size()==0) return 0;map<int,int> mp;for(auto x: nums){mp[x]++;}int pre;int l=0,r=0,res=0;for(auto x=mp.begin();x!=mp.end();x++){if(x==mp.begin()){pre = x->first;l=0;r=0;continue;}if(x->first==pre+1){r++;}else{res=max(res,r-l+1);l=r;}pre = x->first;}return max(res,r-l+1);}
};
解法2: unordered_set，符合要求
class Solution {
public:int longestConsecutive(vector<int>& nums) {if (nums.size()==0) return 0;unordered_set<int> s;for(auto x: nums) s.insert(x);int res =0;for(int x: s){// 如果x不是某连续序列的起点if(s.contains(x-1)){continue;}int y = x+1;while(s.contains(y)){y++;}res = max(y-x,res);}return res;}
};
时间复杂度对比
- 解法 1：时间复杂度为 O(n log n)
因为 map 的插入操作是 O (log n)，n 个元素总插入时间为 O (n log n)。
后续遍历是 O (n)，整体受限于排序步骤，不满足题目要求的 O (n) 时间复杂度。 - 解法 2：时间复杂度为 O(n)
unordered_set 的插入和查找都是 O (1)（平均情况）。
每个元素最多被访问 2 次（一次作为起点遍历，一次被其他起点检查），整体为 O (n)，满足题目要求。
)
