128. 最长连续序列-LeetCode(C++)

128. 最长连续序列

2024.9.12
题目

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

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

示例

示例 1：

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

复制代码

示例 2：

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

复制代码

反思

1.总结一下目前哈希表的应用：

• 可以存储数组元素的出现次数
  
• 可以存储数组元素的下标
  
• 可以存储最长连续序列
  

2.我们可以发现，键值对的值，绝大时候都是直接和题目要求的输出保持一致
3.哈希表的键相邻，值之间有肯定的通报性，可以不断更新，如本题题解1。
4.慎重考虑界限情况！！！包罗传入空数组。
题解1-利用哈希表相邻与否，更新键值对

本题解是目前为止见过的哈希表利用很机动很奇妙的。
用哈希表的键来存储数组元素，这很常见，前面几题都是一样的思路。
用哈希表的值来存储题目要求的“最长连续序列”，经过肯定的积累也是可以联想到的。
本题解焦点在于：当两个键相邻的时候，可以更新哈希表各个值的数值，从而达到O(n)的时间复杂度。

1. class Solution {
2. public:
3.     int longestConsecutive(vector<int>& nums) {
4.         int max_length = 0;//边界条件，可能传入空数组
5.         std::unordered_map<int,int> hashmap;
6.         for(const auto &c : nums){
7.             if(hashmap.find(c) != hashmap.end()){
8.                 continue;
9.             }
10.             int left = 0;
11.             int right = 0;
12.             if(hashmap.find(c-1) != hashmap.end()){
13.                 //找到了前一个
14.                 left = hashmap[c-1];
15.             }
16.             if(hashmap.find(c+1) != hashmap.end()){
17.                 //找到了后一个
18.                 right = hashmap[c+1];
19.             }
20.             hashmap[c] = 1+left+right;
21.             if(max_length < hashmap[c]){
22.                 max_length = hashmap[c];
23.             }
24.             //这里本来应该让从hashmap[c-left]到hashmap[c+right]的值都为1+left+right的
25.             //但是，新加入的键值对只会和前后相邻的元素交互，也就是，中间的部分，值为多少都不影响，那么干脆就不改了
26.             hashmap[c-left] = 1+left+right;
27.             hashmap[c+right] = 1+left+right;
28.         }
29.         return max_length;
30.     }
31. };

复制代码

题解2-利用unordered_set相邻与否，直接数数

来自力扣官方题解
本题焦点在于：先将全部值传入unordered_set，然后每个数都判定一次这个数是不是连续序列的开头那个数，假如是就今后一直数。
仅仅利用了unordered_set部门特性：

• 值的唯一性————可以用往复重
  
• 快速访问————插入、查找和删除操纵上都能提供平均时间复杂度为 O(1) 的性能
  

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.                 //如果num - 1不存在在集和内，那么这个数（num）是连续序列的开头那个数
14.                 int currentNum = num;
15.                 int currentStreak = 1;
17.                 while (num_set.count(currentNum + 1)) {
18.                     currentNum += 1;
19.                     currentStreak += 1;
20.                 }
22.                 longestStreak = max(longestStreak, currentStreak);
23.             }
24.         }
26.         return longestStreak;           
27.     }
28. };

复制代码

增补——unordered_set

以下是 unordered_set 的一些关键特性：

• 唯一性：unordered_set 中的每个元素都是唯一的，不允许有重复的元素。
  
• 无序性：元素在容器中没有特定的次序。假如你必要有序的元素，应该利用 set 而不是 unordered_set。
  
• 快速访问：由于是基于哈希表实现的，unordered_set 提供了快速的访问时间。
  
• 键值对：在 unordered_set 中，键和值是相同的，即每个元素既是键也是值。
  
• 迭代器：unordered_set 提供了迭代器，可以用于遍历容器中的全部元素。
  
• 哈希函数：unordered_set 利用哈希函数来计算元素的存储位置。默认情况下，它利用元素的内置哈希函数，但你也可以提供自界说的哈希函数。
  
• 键值比较：unordered_set 倒霉用比较函数来比较元素，因为它不关心元素之间的次序。
  
• 内存利用：由于哈希表的特性，unordered_set 可能会利用比 set 更多的内存。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。