网站建设咨询服务商_我的主页制作代码_seo软件定制_谷歌手机版下载安装

合并两个有序数组

你有两个按非递减顺序排列的整数数组：

nums1，长度为 m + n，其中前 m 个元素是有效的数字，后面的 n 个元素为 0，需要忽略。
nums2，长度为 n，包含了 n 个有效的数字。

你的任务是将 nums2 中的元素合并到 nums1 中，使得合并后的数组仍然按非递减顺序排列。

注意：

你不需要返回新的数组，而是直接修改 nums1 数组，使其包含合并后的结果。
nums1 有足够的空间（长度为 m + n）来容纳来自 nums2 的元素。

输入参数

nums1: number[] - 第一个数组，长度为 m + n。
m: number - nums1 中有效元素的数量。
nums2: number[] - 第二个数组，长度为 n。
n: number - nums2 中元素的数量。

任务目标

将 nums2 中的元素合并到 nums1 中，使得 nums1 按非递减顺序排列。

示例

示例 1：

输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3输出：
nums1 = [1,2,2,3,5,6]

解释：

初始 nums1 的前 m=3 个元素是 [1,2,3]，后面有三个 0，可用于填充。
nums2 是 [2,5,6]。
合并后，nums1 变为 [1,2,2,3,5,6]。

解决思路

为了在不使用额外空间的情况下合并两个数组，我们可以从两个数组的末尾开始比较和插入。这种方法称为 逆向双指针法。

步骤：

初始化指针：
- i = m - 1：指向 nums1 中最后一个有效元素。
- j = n - 1：指向 nums2 中最后一个元素。
- k = m + n - 1：指向 nums1 的末尾位置。
逆向遍历：
- 比较 nums1[i] 和 nums2[j]。
- 将较大的值放入 nums1[k]，然后移动相应的指针和 k。
处理剩余元素：
- 如果 nums2 中还有剩余元素（j >= 0），需要将它们全部复制到 nums1 中。
- 如果 nums1 中还有剩余元素（i >= 0），不需要处理，因为它们已经在正确的位置上。

代码详解

function merge(nums1: number[], m: number, nums2: number[], n: number): void {let i = m - 1; // nums1 的有效元素的最后一个索引let j = n - 1; // nums2 的最后一个索引let k = m + n - 1; // nums1 的最后一个位置索引// 从后往前遍历，比较并插入较大的元素while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k] = nums1[i]; // 将较大的 nums1[i] 放到 nums1[k]i--; // 移动 nums1 的指针} else {nums1[k] = nums2[j]; // 将较大的 nums2[j] 放到 nums1[k]j--; // 移动 nums2 的指针}k--; // 移动合并后数组的指针}// 如果 nums2 中还有剩余元素，复制到 nums1while (j >= 0) {nums1[k] = nums2[j];j--;k--;}// 不需要处理 nums1 中剩余的元素，它们已经在正确的位置上
}