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

news/2024/12/22 2:24:57/

leetcode.cn/problems/longest-consecutive-sequence/" rel="nofollow">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.ppmy.cn/news/1526944.html

相关文章

DFS:深搜+回溯+剪枝实战解决OJ问题

✨✨✨学习的道路很枯燥&#xff0c;希望我们能并肩走下来! 文章目录 目录 文章目录 前言 一 排列、子集问题 1.1 全排列I 1.2 子集I 1.3 找出所有子集的异或总和 1.4 全排列II 1.5 字母大小写全排列 1.6 优美的排列 二 组合问题 2.1 电话号码的数字组合 …

git编译安装报错

编译安装步骤 卸载旧的 yum -y remove gitcd /usr/local/src/wget https://www.kernel.org/pub/software/scm/git/git-2.15.1.tar.xztar -vxf git-2.15.1.tar.xzcd git-2.15.1make prefix/usr/local/git allmake prefix/usr/local/git installecho "export PATH$PATH:/usr…

【无人机设计与控制】四旋翼无人机俯仰姿态保持模糊PID控制(带说明报告)

摘要 为了克服常规PID控制方法在无人机俯仰姿态控制中的不足&#xff0c;本研究设计了一种基于模糊自适应PID控制的控制律。通过引入模糊控制器&#xff0c;实现了对输入输出论域的优化选择&#xff0c;同时解决了模糊规则数量与控制精度之间的矛盾。仿真结果表明&#xff0c;…

[苍穹外卖]-12Apache POI入门与实战

工作台 需求分析: 工作台是系统运营的数据看板, 并提供快捷操作入口, 可以有效提高商家的工作效率 营业额: 已完成订单的总金额有效订单: 已经完成订单的数量订单完成率: 有效订单数/总订单数*100%平均客单价: 营业额/有效订单数新增用户: 新增的用户数量 接口设计: 一个接口返…

Go语言并发编程:从理论到实践

并发是计算机科学领域中的一个核心概念&#xff0c;但对于不同的人来说&#xff0c;它可能意味着不同的东西。除了“并发”之外&#xff0c;你可能还听说过“异步”、“并行”或“多线程”等术语。一些人认为这些词是同义的&#xff0c;而另一些人则严格区分它们。如果我们要花…

docker时区修改

1、服务器时区 [rootiZwz98l9o3v7h8t5rd0sn5Z ~]# date Wed Sep 4 13:34:46 CST 2024 2、容器时区 [rootiZwz98l9o3v7h8t5rd0sn5Z ~]# docker exec -it openresty /bin/bash root0aabeb13c120:/# date Wed Sep 4 05:36:17 UTC 2024 3、修改容器时区 ln -sf /usr/share/zone…

Python 解析 JSON 数据

1、有如下 JSON 数据&#xff0c;存放在 data.json 文件&#xff1a; [{"id":1, "name": "小王", "gender": "male", "score": 96.8}, {"id":2, "name": "小婷", "gender&qu…

使用Python实现深度学习模型:智能家庭安防系统

随着科技的进步和人们对安全需求的增加,智能家庭安防系统成为了现代家庭的重要组成部分。通过深度学习技术,我们可以构建高效的智能安防系统,实时监测家庭环境,识别潜在威胁,并提供及时的预警。本文将详细介绍如何使用Python实现一个简单的深度学习模型,用于智能家庭安防…