『前端算法』数组-合并两个有序数组
题目描述
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
思路分析
该题标准解法用双指针法,首先定义两个指针,各指向两个数组生效部分的尾部。每次只对指针所指的元素进行比较。 取其中较大的元素,把它从num1的尾部往前填充。
由于num1的有效部分和num2不一定一样长,我们需要考虑提前一个先遍历完的情况:
- 如果num1的有效部分提前遍历完,那么num2剩下的部分直接补充到num1前面空出来的位置;
- 如果num2的有效部分提前遍历完,剩下的是num1的部分,由于容器都是num1的,所以就不需要处理了。
代码实现
标准代码如下:
/**
* @params {Array} num1
* @params {Number} m num1的数组长度
* @params {Array} num2
* @params {Number} n num2的数组长度
* @return {Array} 返回num1数组
* */
const merge = function(num1,m,num2,n) {
// 初始化两个指针指向,初始化num1的最大索引为k
let i = m - 1, j = n - 1, k = m + n - 1;
// 当两个数组都没有遍历完成时,指针同步移动
while(i >=0 && j >= 0) {
// 取较大值往num1末尾往前填
if(num1[i] >= num2[j]) {
num1[k] = num1[i];
k--;
i--;
} else {
num1[k] = num2[j];
k--;
j--;
}
}
// num2未遍历完情况
while(j >= 0) {
num1[k] = num2[j];
k--;
j--;
}
return num1;
}
调用:
const num1 = [1,2,3];
const num2= [2,5,6];
console.log(merge(num1,3,num2,3)) // [1,2,2,3,5,6]