做一个静态网站多少钱,企业微信公众号平台官网,建设o2o网站,金华哪里做网站文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一#xff1a;排序方法二#xff1a;哈希表 5.实现示例参考文献 1.问题描述
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你… 文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一排序方法二哈希表 5.实现示例参考文献 1.问题描述
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 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]
输出92.难度等级
medium。
3.热门指数
★★★★☆
出题公司阿里、腾讯、百度、字节。
4.解题思路
方法一排序
根据本题的描述一般来说最容易想到的就是先将 nums 进行排序然后再从排序后的数组头部开始遍历如果存在nums[i]1则进行加1计数。只要不存在 nums[i]1则从 0 开始重新执行计数操作。那么每当发生了“断点”如果当前连续序列长度大于 result 则更新 result 值result 表示最长连续序列的长度。
但是由于本题目要求实现时间复杂度为 O(n) 的算法解决此问题那么排序的做法我们就无法实现了。那么我们还有什么别的方法来解决这道题吗
方法二哈希表
我们考虑枚举数组中的每个数 x考虑以其为起点不断判断 x1,x2,⋯x1, x2,⋯ 是否存在假设最长匹配到了 xy其长度为 y1我们不断枚举并更新答案即可。
对于匹配的过程暴力的方法是 O(n) 遍历数组去看是否存在这个数但其实更高效的方法是用一个哈希表存储数组中的数这样查看一个数是否存在即能优化至 O(1) 的时间复杂度。
仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 O(n^2)当整个数组为最长序列外层需要枚举 O(n) 个数内层需要暴力匹配 O(n) 次无法满足题目的要求。但仔细分析这个过程我们会发现其中执行了很多不必要的枚举如果已知有一个 x,x1,x2,⋯ ,xy 的连续序列而我们却重新从 x1x2 或者是 xy 处开始尝试匹配那么得到的结果肯定不会优于枚举 x 为起点的答案因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1。不然按照上面的分析我们会从 x−1 开始尝试匹配因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
增加了判断跳过的逻辑之后时间复杂度是多少呢外层循环需要 O(n) 的时间复杂度只有当一个数是连续序列的第一个数的情况下才会进入内层循环然后在内层循环中匹配连续序列中的数因此数组中的每个数只会进入内层循环一次。根据上述分析可知总时间复杂度为 O(n)符合题目要求。
5.实现示例
下面以 Golang 为例给出上面的实现。
注意Golang 中如果哈希表只有 key 没有 value建议使用 map[any]struct{}因为空结构体不占用内存空间。
func longestConsecutive(nums []int) int {m : make(map[int]struct{}, len(nums))for _, n : range nums {m[n] struct{}{}}var longestStreak intfor x : range m {// 跳过逻辑if _, ok : m[x-1]; ok {continue}// 计算连续子序列长度y : x 1for ;;y{if _, ok : m[y]; !ok {break}}if y - x longestStreak {longestStreak y-x}}return longestStreak
}LeetCode 运行结果如下 参考文献
128. 最长连续序列 - leetcode
