❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!
- 推荐:数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航:
- LeetCode解锁1000题: 打怪升级之旅:每题都包括3-5种算法,以及详细的代码实现,刷题面试跳槽必备
- 漫画版算法详解:通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读,看一遍就掌握
- python源码解读:解读python的源代码与调用关系,快速提升代码质量
- python数据分析可视化:企业实战案例:企业级数据分析案例与可视化,提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用:全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
题目描述
给定一个未排序的整数数组 nums
,找出数字连续的最长序列的长度。要求时间复杂度在 O(n) 内。
注意:
- 这个序列不需要在原数组中是连续的。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度是 4。
方法一:哈希表
解题步骤
- 使用哈希表存储所有数字,以便快速查找数组中的任意数字是否存在。
- 遍历数组
nums
,对每个元素进行检查:
- 如果其前一个元素
(num - 1)
不在哈希表中,则这是一个新序列的起点。
- 从起点开始,递增查找连续的数字,同时更新最长连续序列的长度。
- 返回找到的最大长度。
Python 示例
def longestConsecutive(nums): num_set = set(nums) max_length = 0 for num in num_set: if num - 1 not in num_set: current_num = num current_length = 1 while current_num + 1 in num_set: current_num += 1 current_length += 1 max_length = max(max_length, current_length) return max_length # 示例使用 nums = [100, 4, 200, 1, 3, 2] print(longestConsecutive(nums)) # 输出: 4
算法分析
- 时间复杂度:O(n)。尽管看起来有双层循环,但每个数字在内层循环中只访问一次。
- 空间复杂度:O(n),因为需要存储数组元素的哈希表。
详细步骤说明
- 构建哈希表:
- 将所有数字插入哈希表,确保每个数字能被快速查找。
- 例如,对于输入
[100, 4, 200, 1, 3, 2]
,哈希表为{100, 4, 200, 1, 3, 2}
。
- 查找序列起点:
- 遍历哈希表中的每个数字,判断是否为序列的起点。
- 一个数字是序列起点的条件是其前一个数字不在哈希表中。
- 例如,
1
是起点,因为0
不在哈希表中。
- 构建序列:
- 从序列起点开始,逐步查找下一个连续数字,并计算序列长度。
- 例如,从
1
开始,可以找到2
、3
和4
,最终序列长度为4
。
更多示例
- 输入:
[0, -1, 1, 2, 3]
- 输出:
5
- 解释:最长连续序列是
[-1, 0, 1, 2, 3]
,长度为5
。
- 输入:
[10, 5, 12, 3, 55, 6, 11, 8, 7, 9]
- 输出:
6
- 解释:最长连续序列是
[5, 6, 7, 8, 9, 10]
,长度为6
。
图示与说明
考虑 nums = [100, 4, 200, 1, 3, 2]
:
- 构建哈希表:
- 哈希表:
{100, 4, 200, 1, 3, 2}
- 查找序列起点:
初始数组: [100, 4, 200, 1, 3, 2] 哈希表构建: {100, 4, 200, 1, 3, 2} 从 '1' 开始,因为 '0' 不在集合中,序列可以从 '1' 开始向上构建: 1 -> 2 -> 3 -> 4 连续序列长度为 4,是此数组的最长连续序列。
- 详细步骤说明:
步骤 | 当前数字 | 当前序列 | 最长序列长度 |
初始 | [100, 4, 200, 1, 3, 2] | ||
构建哈希表 | {100, 4, 200, 1, 3, 2} | ||
步骤1 | 1 | [1] | 1 |
步骤2 | 1 -> 2 | [1, 2] | 2 |
步骤3 | 1 -> 2 -> 3 | [1, 2, 3] | 3 |
步骤4 | 1 -> 2 -> 3 -> 4 | [1, 2, 3, 4] | 4 |
🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)
❤️❤️作者知识有限,如有错误,请各位大佬评论区批评指正,不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉