原題鏈接： 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)，滿足題目要求。
)
