内容简介:给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为输入:[100, 4, 200, 1, 3, 2]解释:最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
给定一个未 排序 的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n) 。
示例:
输入:[100, 4, 200, 1, 3, 2]
输出: 4
解释:最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路
- 连续序列,首先要对传入数组进行 排序
-
连续序列的标志为
s[n] - s[n-1] === 1
,针对这个来进行循环判断 -
定义循环中的最大长度
num
以及最终长度max
,每次需取max(num, max)
- 当 s[n] - s[n-1] !== 1 时,及连续序列断开,需重置当前最大长度
- 特殊用例情况:[1,2,2,3]中的连续序列为[1,2,3],长度为3。因此在循环中当s[n] === s[n-1]时候,应跳过
直接上代码
/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { if (!nums.length) return 0; var sortedNums = nums.sort((a,b) => (a - b)); var i = 1; var num = 1; var max = 1; while(i < sortedNums.length) { if (sortedNums[i] - sortedNums[i - 1] === 1) { num++; } else if (sortedNums[i] === sortedNums[i - 1]) { i++; continue; } else { num = 1; } max = Math.max(max, num); i++; } return max }; 复制代码
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
美团机器学习实践
美团算法团队 / 人民邮电出版社 / 2018-8-1 / 79.00元
人工智能技术正以一种超快的速度深刻地改变着我们的生活,引导了第四次工业革命。美团作为国内O2O领域领 先的服务平台,结合自身的业务场景和数据,积极进行了人工智能领域的应用探索。在美团的搜索、推荐、计算广告、风控、图像处理等领域,相关的人工智能技术得到广泛的应用。本书包括通用流程、数据挖掘、搜索和推荐、计算广告、深度学习以及算法工程6大部分内容,全面介绍了美团在多个重要方面对机器学习的应用。 ......一起来看看 《美团机器学习实践》 这本书的介绍吧!