网站开发验收报告模板,wordpress 仿站 主题,免费看的logo图片,微信网站 影楼给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1#xff1a; 输入#xff1a;nums [100,4,200,1,3,2] 输出#xff1a;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 错误题解:
/*** param {number[]} nums* return {number}*/
var longestConsecutive function(nums) {if(nums.length0) return 0sort_numsnums.sort(function(a,b){return a-b})let i 0let arr_length1let final_length[]while(isort_nums.length){if(sort_nums[i]sort_nums[i1]-1){arr_lengthi}else{final_length.push(arr_length)arr_length1i}}final_length.sort(function (a, b) {return a - b})let result final_lengthreturn result[result.length-1]
};未处理当两个相同数字处在连续数字中间的情况,修改后:
/*** param {number[]} nums* return {number}*/
var longestConsecutive function(nums) {if(nums.length0) return 0sort_numsnums.sort((a, b) a - b )let i 0let arr_length1let final_length[]while(isort_nums.length){if(sort_nums[i]sort_nums[i1]-1){arr_length}else if(sort_nums[i]sort_nums[i1]){}else{final_length.push(arr_length)arr_length1}i}final_length.sort((a, b) a - b )let result final_lengthreturn result[result.length-1]
};能通过,但时间复杂度是O(nlogn),谈谈思路并优化代码结构:
从小到大排序数组nums遍历数组,遇到连续增大的项则arr_length加1,遇到相同的项则不做处理遇到不连续的项则将arr_length的值记录在新数组中,并将arr_length重置为1。新思路是每次循环都更新最大的arr_length值,和我的思路不太一样,我的思路是将数组每次不连续时的值都存在finally_arr数组中,最后再进行一个比较,取出最大的arr_length。
优化代码后
var longestConsecutive (nums) {if (nums.length 0) return 0nums.sort((a, b) a - b)let max 1let count 1for (let i 0; i nums.length - 1; i) {let cur i, next i 1if (nums[cur] nums[next]) continue // 相同就跳过本次循环if (nums[cur] 1 nums[next]) { // 发现连续项 countcount} else { // 否则count重置1count 1}max Math.max(max, count)}return max
}思路2
方法2Set 的查找是 O(1)
查找 Set 中的元素的时间复杂度是 O(1)JS 的 Set 能给数组去掉重复元素将数组元素存入 set 中遍历数组 nums如果 当前项 - 1 存在于 set 说明当前项不是连续序列的起点跳过继续遍历当前项没有“左邻居”它就是连续序列的起点不断在 set 中查看 cur 1 是否存在存在则 count 1cur 不再有 “右邻居” 了就算出了一段连续序列的长度
代码
var longestConsecutive (nums) {const set new Set(nums) // set存放数组的全部数字let max 0for (let i 0; i nums.length; i) {if (!set.has(nums[i] - 1)) { // nums[i]没有左邻居是序列的起点let cur nums[i]let count 1while (set.has(cur 1)) { // cur有右邻居cur1cur // 更新curcount }max Math.max(max, count) // cur不再有右邻居检查count是否最大}}return max
}作者笨猪爆破组
链接https://leetcode.cn/problems/longest-consecutive-sequence/solutions/277084/fang-fa-cong-yi-dao-nan-bing-cha-ji-fang-fa-bu-hui/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。方法3哈希表
来源于力扣大佬
哈希表的value存什么key存数字value存什么新存入的数字如果它找到相邻的数它希望从邻居数那里获取什么信息很显然它希望左邻居告诉它左边能提供的连续长度右邻居告诉它右边能提供的连续长度加上它自己的长度就有了自己处在的连续序列的长度
更新新序列的两端数字的value
同处一个连续序列的数字的value理应都相同这是它们共同特征 但没有必要每个的value都是序列长度只需要两端的数存序列的长度就好 因为靠的是两端和新数对接序列是连续的中间没有空位 序列的一端找到邻居后将另一端对应的value更新为最新的序列长度 方法3 代码
var longestConsecutive (nums) {let map new Map()let max 0for (const num of nums) { // 遍历nums数组if (!map.has(num)) { // 重复的数字不考察跳过let preLen map.get(num - 1) || 0 // 获取左邻居所在序列的长度 let nextLen map.get(num 1) || 0 // 获取右邻居所在序列的长度 let curLen preLen 1 nextLen // 新序列的长度map.set(num, curLen) // 将自己存入 mapmax Math.max(max, curLen) // 和 max 比较试图刷新maxmap.set(num - preLen, curLen) // 更新新序列的左端数字的valuemap.set(num nextLen, curLen) // 更新新序列的右端数字的value}}return max
}作者笨猪爆破组
链接https://leetcode.cn/problems/longest-consecutive-sequence/solutions/277084/fang-fa-cong-yi-dao-nan-bing-cha-ji-fang-fa-bu-hui/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
