题目描述
题目描述
给定一个无序整型数组,请找出最长的连续整数序列。
要求使用 $O(n)$ 时间复杂度的算法。
样例
输入
[100, 4, 200, 1, 3, 2]
输出
4
解释:最长的连续整数序列是 [1, 2, 3, 4],其长度是4。
算法
(哈希) $O(n)$
首先将所有数字放入哈希表,遍历哈希表中的元素,因为要找连续的数字序列,因此可以通过向后枚举相邻的数字(即不断加一),判断后面一个数字是否在哈希表中即可。
为了保证$O(n)$的复杂度,为了避免重复枚举序列,因此只对序列的起始数字向后枚举(例如[1,2,3,4]
,只对1枚举,2,3,4时跳过),因此需要判断一下是否是序列的起始数字(即判断一下n-1是否在哈希表中)。
时间复杂度
$O(n)$
C++ 代码
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> hash(nums.begin(), nums.end());
int len = 0;
for (auto num : hash) {
if (hash.find(num - 1) == hash.end()) { // 只考虑连续序列的起始元素,避免重复遍历序列
int end = num;
while (hash.find(end) != hash.end())
end += 1;
len = max(end - num, len);
}
}
return len;
}
};
我好奇为什么不用S.count(), 因为unordered_set已经去重,只存在有或者没有的情况。即0和1
特判条件很精彩
hash.find(num - 1) == hash.end()//这句话太牛批了
妙啊
妙个崔子
妙啊
妙个崔子
这里是直接枚举hash表里的数, 已经去过重了, 棒 :thumb:
怎么感觉这种方法会有O(n^2)复杂度呢?因为while那儿会有O(n)。
if (hash.find(num - 1) == hash.end())
这里保证了只考虑连续序列的起始元素,因此不会是O(n^2)