LeetCode系列之 (JavaScript) => 88. 合并两个有序数组
2022/3/3 17:16:14
本文主要是介绍LeetCode系列之 (JavaScript) => 88. 合并两个有序数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
【Leetcode 题目链接】:88. 合并两个有序数组 - 力扣(LeetCode) (leetcode-cn.com)
解题思路分析:
- 在nums1中找到nums2 插入的位置,然后在整体排序;
- 或采用合并排序的方式,逐个位置判断需要插入的元素(还要考虑循环方向,比如下面的第三种解法);
- 由于m,n的大小不确定,所以还需要考虑覆盖和其中一个数组没有遍历结束的情况;
不同解法:
/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ // 利用的是Array里面的自带方法 - 方便熟悉 var merge = function(nums1, m, nums2, n) { nums1.splice(m,n,...nums2); // 插入nums2 nums1.sort((a,b) => a-b); // 整体排序 }; // 使用三个指针进行排序,时间复杂度是O(n^2) var merge = function(nums1, m, nums2, n){ if(nums2.length == 0){ return; } var k = 0, i = 0, j = 0; // k 表示插入的位置,i遍历nums1,j遍历nums2 var newNums1 = nums1.slice(0,m); for(k ; k < m+n; k++){ // 如果 nums2 遍历结束,将 nums1 直接加入 if(j == n){ while(i < m){ nums1[n+i] = newNums1[i]; i++; } // console.log(nums1) return; } // 如果 nums1 遍历结束,将 nums2 直接加入 if(i == m){ while(j < n){ nums1[m+j] = nums2[j]; j++; } // console.log(nums1) return; } if(newNums1[i] <= nums2[j]){ nums1[k] = newNums1[i++]; }else{ nums1[k] = nums2[j++]; } } } // 【继续改进】 -> 将nums1中需要排序的m个元素插入到尾部 -> 不用考虑如果nums2提前遍历完的情况 // 循环结束条件:nums2循环遍历完,不用考虑nums1遍历完 var merge = function(nums1, m, nums2, n){ //将nums1中需要排序的m个元素插入到尾部 //循环方向从后往前,如果m>n,就会有“重叠”,从前往后循环,就会造成覆盖,移动就会造成问题 for(var count = 1; count <= m ; count++){ nums1[m+n-count] = nums1[m-count]; } //遍历 nums2 var i = n; // 用来遍历nums1 var j = 0; // 用来遍历nums2 var k = 0; // 代表插入的位置 while(j < n){ //如果遍历nums1结束,直接将nums2 加到最后 (这一块【可加可不加】,提交都能通过) if(k == m+j){// 或条件设为 i == n+m while(j < n){ nums1[k++] = nums2[j++]; } return; } if(nums1[i] <= nums2[j]){ nums1[k] = nums1[i++]; }else{ nums1[k] = nums2[j++]; } k++; } } // 【继续改进】:从nums1的末尾开始,比较两个数组最大的值 // 循环方向从后向前,同样可以防止覆盖 var merge = function(nums1, m, nums2, n){ var i = m-1,j = n-1,k = m+n-1; while(i >= 0 && j >= 0){ if(nums1[i] > nums2[j]){ nums1[k--] = nums1[i--]; }else{ nums1[k--] = nums2[j--]; } } while(j >= 0){ nums1[k--] = nums2[j--]; } }
参考链接:
- 88. Merge Sorted Array · leetcode
- This is my AC code, may help you - LeetCode Discuss
这篇关于LeetCode系列之 (JavaScript) => 88. 合并两个有序数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?