力扣DAY3 | 热100 | 最长连续序列

媒介

中等 √ 本日的题确实想了好一会儿，第一次超时第二次解出来了。但奇怪的是反而第一次的解法是O(n)，第二次O(nlog）。
题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1. <strong>输入：</strong>nums = [100,4,200,1,3,2]
2. <strong>输出：</strong>4
3. <strong>解释：</strong>最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

复制代码

示例 2：

1. <strong>输入：</strong>nums = [0,3,7,2,5,8,4,6,0,1]
2. <strong>输出：</strong>9

复制代码

示例 3：

1. <strong>输入：</strong>nums = [1,0,1,2]
2. <strong>输出：</strong>3

复制代码

提示：

• 0 <= nums.length <= 105
  
• -109 <= nums <= 109
  

思路

思路一：把数组存进哈希聚集去重，从最小的数到最大的数逐个遍历是否在哈希表中，同时记录连续序列号。
思路二：先对数组举行排序，从第一位开始遍历，查询哈希表是否存在该数的前一位，如有则以该数为键，前一位的值+1为值存入（这个值就是当前的连续序列），没有则以该数为键，“1”为值存入。最后遍历哈希表找出最大值。
我的题解

思路一（复杂度为O(n)但超时）

1. class Solution {
2. public:
3.     int longestConsecutive(vector<int>& nums) {
4.         
5.         if(nums.empty())
6.             return 0;
8.         unordered_set<int> map(nums.begin(),nums.end());
9.         int max_len = 0;
10.         int len = 0;
11.         int min_num = *min_element(begin(nums), end(nums));
12.         int max_num = *max_element(begin(nums), end(nums));
14.         for(int i = min_num; i <= max_num; ++i){
16.             auto it = map.find(i);
17.             if(it != map.end()){
18.                 len++;
19.                 if(len >= max_len)
20.                     max_len = len;
21.             }else{
22.                 len = 0;
23.             }
24.                
25.         }
27.         return max_len;
29.     }
30. };

复制代码

思路二（因为由排序操纵以是复杂度为O(nlog)，ac）

1. class Solution {
2. public:
3.     int longestConsecutive(vector<int>& nums) {
4.         
5.         if(nums.empty())
6.             return 0;
8.         sort(nums.begin(), nums.end());
10.         unordered_map<int,int> map;
11.         int max_len = 1;
12.         
13.         map[nums[0]] = 1;
15.         for(int i = 1; i < nums.size(); i++){
16.             
17.             auto it = map.find(nums[i]-1);
18.             if(it != map.end()){
19.                 map[nums[i]] = it->second + 1;
20.             }else{
21.                 map[nums[i]] = 1;
22.             }
24.         }
26.         for(auto& element:map){
27.             if(element.second > max_len)
28.                 max_len = element.second;
29.         }
30.         return max_len;
32.     }
33. };

复制代码

官方题解

我们考虑枚举数组中的每个数 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)，符合题目要求。

1. class Solution {
2. public:
3.     int longestConsecutive(vector<int>& nums) {
4.         unordered_set<int> num_set;
5.         for (const int& num : nums) {
6.             num_set.insert(num);
7.         }
9.         int longestStreak = 0;
11.         for (const int& num : num_set) {
12.             if (!num_set.count(num - 1)) {
13.                 int currentNum = num;
14.                 int currentStreak = 1;
16.                 while (num_set.count(currentNum + 1)) {
17.                     currentNum += 1;
18.                     currentStreak += 1;
19.                 }
21.                 longestStreak = max(longestStreak, currentStreak);
22.             }
23.         }
25.         return longestStreak;           
26.     }
27. };

复制代码

哈希表知识点

分为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企服之家，中国第一个企服评测及商务社交产业平台。