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)\)