东莞中高端网站建设,宝塔面板怎么做多个网站,广州移动 网站设计,下载做网站ftp具体步骤题目#xff1a;最长连续序列
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1#xff1a; 输入#xff1a;nums [100,4,…题目最长连续序列
给定一个未排序的整数数组 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] 输出9
提示 0 nums.length 105 -109 nums[i] 109
我们做算法题的时候一定先审好题题目要求找出数字连续的最长序列不要求序列元素在原数组中的连续的长度。 其中的关键点是不要求在原数组的连续所以我们可以进行先进行去重和排序。
解题思路
这道题的关键点在于如何识别并统计出最长的连续数字序列。我们可以采用以下步骤来解决问题
去重与排序首先我们需要去除数组中的重复元素并对其进行排序。这是因为连续序列的元素在排序后会相邻且去重可以避免重复计算同一个数字。先用new Set去重再用sort进行排序遍历排序后的数组然后遍历排序后的数组逐个检查每个数字是否可以延伸出一个更长的连续序列这里的关键思路是从数组中的第二个值开始遍历对于当前的数字如果前一个数字与当前数字相差为1说明是连续的。就把它加入到当前的连续序列中否则它就作为新序列的起始点。记录最长序列长度在遍历过程中不断更新最长序列的长度。并在遍历结束后返回这个长度。
JavaScript实现
/*** param {number[]} nums* return {number}*/
var longestConsecutive function (nums) {// 先判断是否为一个空数组如果是就返回0if (nums.length 0) return 0;// 先去重再排序然后得到一个每个数字具有唯一性的数组let uniqueNums Array.from(new Set(nums)).sort((a, b) a - b)// 接着声明最长数字连续序列长度为1然后需要声明一个存储当前长度的变量初始化值为1let maxLength currentLength 1;// 数组经过去重排序之后接着进行遍历数组如果数组当前值与前一个值相差为1说明是连续的当前长度加currentLength加1。// 如果不相等则重新比较maxLength与currentLength值最大的赋值给maxLengthcurrentLength则重新开始从1算起。for (let i 1; i uniqueNums.length; i) {if (uniqueNums[i] uniqueNums[i - 1] 1) {currentLength; // 如果数组当前值与前一个值相差为1说明是连续的当前长度加currentLength加1} else {// 如果不相等则重新比较maxLength与currentLength值最大的赋值给maxLengthcurrentLength则重新开始从1算起。maxLength Math.max(maxLength, currentLength);currentLength 1;}}// 最后再比较一下最大长度值和当前长度值得出最后的最大长度。为什么最后再比较一下呢// 因为在上面的循环中只有在else中maxLength才会进行更新如果是一直在if中maxLength就不会进行更新所以最后需要重新比较一下。maxLength Math.max(maxLength, currentLength);return maxLength;
}
