128. 最长连续序列-LeetCode(C++)
128. 最长连续序列2024.9.12
题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法办理此题目。
提示：
[*]0 <= nums.length <= 105
[*]-109 <= nums <= 109
示例
示例 1：
输入：nums =
输出：4
解释：最长数字连续序列是 。它的长度为 4。
示例 2：
输入：nums =
输出：9
反思
1.总结一下目前哈希表的应用：
[*]可以存储数组元素的出现次数
[*]可以存储数组元素的下标
[*]可以存储最长连续序列
2.我们可以发现，键值对的值，绝大时候都是直接和题目要求的输出保持一致
3.哈希表的键相邻，值之间有肯定的通报性，可以不断更新，如本题题解1。
4.慎重考虑界限情况！！！包罗传入空数组。
题解1-利用哈希表相邻与否，更新键值对
本题解是目前为止见过的哈希表利用很机动很奇妙的。
用哈希表的键来存储数组元素，这很常见，前面几题都是一样的思路。
用哈希表的值来存储题目要求的“最长连续序列”，经过肯定的积累也是可以联想到的。
本题解焦点在于：当两个键相邻的时候，可以更新哈希表各个值的数值，从而达到O(n)的时间复杂度。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int max_length = 0;//边界条件，可能传入空数组
std::unordered_map<int,int> hashmap;
for(const auto &c : nums){
if(hashmap.find(c) != hashmap.end()){
continue;
}
int left = 0;
int right = 0;
if(hashmap.find(c-1) != hashmap.end()){
//找到了前一个
left = hashmap;
}
if(hashmap.find(c+1) != hashmap.end()){
//找到了后一个
right = hashmap;
}
hashmap = 1+left+right;
if(max_length < hashmap){
max_length = hashmap;
}
//这里本来应该让从hashmap到hashmap的值都为1+left+right的
//但是，新加入的键值对只会和前后相邻的元素交互，也就是，中间的部分，值为多少都不影响，那么干脆就不改了
hashmap = 1+left+right;
hashmap = 1+left+right;
}
return max_length;
}
};
题解2-利用unordered_set相邻与否，直接数数
来自力扣官方题解
本题焦点在于：先将全部值传入unordered_set，然后每个数都判定一次这个数是不是连续序列的开头那个数，假如是就今后一直数。
仅仅利用了unordered_set部门特性：
[*]值的唯一性————可以用往复重
[*]快速访问————插入、查找和删除操纵上都能提供平均时间复杂度为 O(1) 的性能
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)) {
//如果num - 1不存在在集和内，那么这个数（num）是连续序列的开头那个数
int currentNum = num;
int currentStreak = 1;
while (num_set.count(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
增补——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企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]