5.合并两个有序数组
合并两个有序数组
题目
给定两个已经按升序排列的整数数组 nums1 和 nums2,以及一个整数 m,nums1 的大小是 m + n,其中前 m 个元素表示已经填入的数字,后面的 n 个元素为 0,表示可以填充的数字个数。nums2 包含 n 个有效元素。你需要将 nums2 中的所有元素按照升序合并到 nums1 中,使得合并后的 nums1 仍然是一个有序数组。
示例
输入:nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出:nums1 被修改为 [1, 2, 2, 3, 5, 6]
参考答案
DETAILS
<script>
function merge(nums1, m, nums2, n) {
// 初始化指针
let p1 = m - 1; // nums1 中已排序部分的最后一个元素索引
let p2 = n - 1; // nums2 中最后一个元素的索引
let p = m + n - 1; // 合并后数组的最后一个元素的索引
// 从后向前合并数组
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
// 如果 nums2 中还有剩余元素,直接复制到 nums1 中
while (p2 >= 0) {
nums1[p] = nums2[p2];
p2--;
p--;
}
// 注意:这里不需要处理 nums1 中剩余的元素,因为题目已说明 nums1 后面是 0,且 nums1 大小足够
}
// 示例用法
let nums1 = [1, 2, 3, 0, 0, 0];
let m = 3;
let nums2 = [2, 5, 6];
let n = 3;
merge(nums1, m, nums2, n);
console.log(nums1); // 输出: [1, 2, 2, 3, 5, 6]
</script>