力扣DAY3 | 热100 | 最长连续序列
媒介中等 √ 本日的题确实想了好一会儿，第一次超时第二次解出来了。但奇怪的是反而第一次的解法是O(n)，第二次O(nlog）。
题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
<strong>输入：</strong>nums =
<strong>输出：</strong>4
<strong>解释：</strong>最长数字连续序列是 。它的长度为 4。 示例 2：
<strong>输入：</strong>nums =
<strong>输出：</strong>9
示例 3：
<strong>输入：</strong>nums =
<strong>输出：</strong>3
提示：
[*]0 <= nums.length <= 105
[*]-109 <= nums <= 109
思路
思路一：把数组存进哈希聚集去重，从最小的数到最大的数逐个遍历是否在哈希表中，同时记录连续序列号。
思路二：先对数组举行排序，从第一位开始遍历，查询哈希表是否存在该数的前一位，如有则以该数为键，前一位的值+1为值存入（这个值就是当前的连续序列），没有则以该数为键，“1”为值存入。最后遍历哈希表找出最大值。
我的题解
思路一（复杂度为O(n)但超时）
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty())
return 0;
unordered_set<int> map(nums.begin(),nums.end());
int max_len = 0;
int len = 0;
int min_num = *min_element(begin(nums), end(nums));
int max_num = *max_element(begin(nums), end(nums));
for(int i = min_num; i <= max_num; ++i){
auto it = map.find(i);
if(it != map.end()){
len++;
if(len >= max_len)
max_len = len;
}else{
len = 0;
}
}
return max_len;
}
}; 思路二（因为由排序操纵以是复杂度为O(nlog)，ac）
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty())
return 0;
sort(nums.begin(), nums.end());
unordered_map<int,int> map;
int max_len = 1;
map] = 1;
for(int i = 1; i < nums.size(); i++){
auto it = map.find(nums-1);
if(it != map.end()){
map] = it->second + 1;
}else{
map] = 1;
}
}
for(auto& element:map){
if(element.second > max_len)
max_len = element.second;
}
return max_len;
}
}; 官方题解
我们考虑枚举数组中的每个数 x，考虑以其为起点，不停尝试匹配 x+1,x+2,⋯ 是否存在，假设最长匹配到了 x+y，那么以 x 为起点的最长连续序列即为 x,x+1,x+2,⋯,x+y，其长度为 y+1，我们不停枚举并更新答案即可。
对于匹配的过程，暴力的方法是 O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，如许检察一个数是否存在即能优化至 O(1) 的时间复杂度。
仅仅是如许我们的算法时间复杂度最坏环境下照旧会到达 O(n2)（即外层必要枚举 O(n) 个数，内层必要暴力匹配 O(n) 次），无法满意题目标要求。但仔细分析这个过程，我们会发现此中实行了很多不须要的枚举，如果已知有一个 x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的效果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时间碰到这种环境跳过即可。
那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，否则按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否必要跳过了。
增加了判断跳过的逻辑之后，时间复杂度是多少呢？外层循环必要 O(n) 的时间复杂度，只有当一个数是连续序列的第一个数的环境下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)，符合题目要求。
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;
}
};
哈希表知识点
分为map和set，此中set是只有键没有值的去重聚集。
与map相比查找和遍历有所差异
3. **查找元素**：
- 使用 `find()` 方法查找元素，如果找到则返回指向该元素的迭代器，否则返回 `mySet.end()`。
- 使用 `count()` 方法检查是否存在某个元素，返回 1 表现存在，0 表现不存在。
```cpp
if (mySet.find(20) != mySet.end()) {
std::cout << "Element found" << std::endl;
}
if (mySet.count(20)) {
std::cout << "Element exists" << std::endl;
}
```
4. **遍历元素**：
可以使用范围 for 循环或者迭代器来遍历 `unordered_set` 中的所有元素。注意，由于哈希表不包管元素的顺序，以是遍历时元素大概不会按照插入顺序出现。
```cpp
for (const auto& elem : mySet) {
std::cout << elem << " ";
}
```
心得
这道题虽然ac但实际上不符合要求，因为使用了排序。而官方题解用了哈希聚集，检查前置数是否在聚集中，不在的话才开始从该数遍历，包管了只有最前的数进入遍历，而不必要排序，这个思路确实没想到。积累！另外我的思路一符合题意范围超出时间了，感觉测试用例不敷全，如果这个数组到一定长度且倒序，相信效果会有区别。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]