当前位置: 首页 > news >正文

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

128. 最长连续序列

2024.9.12

题目

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
示例

示例 1:

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

示例 2:

输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出: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[c-1];}if(hashmap.find(c+1) != hashmap.end()){//找到了后一个right = hashmap[c+1];}hashmap[c] = 1+left+right;if(max_length < hashmap[c]){max_length = hashmap[c];}//这里本来应该让从hashmap[c-left]到hashmap[c+right]的值都为1+left+right的//但是,新加入的键值对只会和前后相邻的元素交互,也就是,中间的部分,值为多少都不影响,那么干脆就不改了hashmap[c-left] = 1+left+right;hashmap[c+right] = 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 的一些关键特性:

  1. 唯一性unordered_set 中的每个元素都是唯一的,不允许有重复的元素。
  2. 无序性:元素在容器中没有特定的顺序。如果你需要有序的元素,应该使用 set 而不是 unordered_set
  3. 快速访问:由于是基于哈希表实现的,unordered_set 提供了快速的访问时间。
  4. 键值对:在 unordered_set 中,键和值是相同的,即每个元素既是键也是值。
  5. 迭代器unordered_set 提供了迭代器,可以用于遍历容器中的所有元素。
  6. 哈希函数unordered_set 使用哈希函数来计算元素的存储位置。默认情况下,它使用元素的内置哈希函数,但你也可以提供自定义的哈希函数。
  7. 键值比较unordered_set 不使用比较函数来比较元素,因为它不关心元素之间的顺序。
  8. 内存使用:由于哈希表的特性,unordered_set 可能会使用比 set 更多的内存。

http://www.mrgr.cn/news/24889.html

相关文章:

  • Day7 | Java框架 | SpringMVC
  • 633. 平方数之和-LeetCode(C++)
  • 认识人工智能(AI,Artificial Intelligence)
  • 多文件编程实现链表创建,插入,输出(上)
  • 期望极大算法(Expectation Maximization Algorithm,EM)
  • C++ STL之set和unordered_set
  • STM32点亮第一个LED
  • Redis 入门 - C#|.NET Core客户端库六种选择
  • 捕获和处理异常非常重要
  • STM32 + W5500 实现HTTPS !
  • Python习题 177:设计银行账户类并实现存取款功能
  • 基于ssm+vue+uniapp的食堂线上预约点餐系统小程序
  • QT QSystemTrayIcon创建系统托盘区图标
  • 2024年增强现实(AR)的现状
  • 每日一题:移动零
  • gdb调试64位程序错误
  • 每日OJ_牛客_合唱团(打家劫舍dp)
  • 【佳学基因检测】在EXCEL中,如何获取A列的第9-29个字符,将其填入另一列中
  • 【MySQL】表的操作【有关表结构的操作】【创建、查看、删除、修改表结构】
  • 【AI赋能医学】基于深度学习和HRV特征的多类别心电图分类