当前位置: 面试刷题>> 合并排序数组Ⅰ (经典算法题500道)


题目描述

合并排序数组Ⅰ

给定两个已排序的整数数组 nums1m + n 个长度的 nums2,其中 nums1 的长度为 mnums2 的长度为 n。将 nums2 中的所有元素合并到 nums1 中,使得 nums1 也变为一个有序数组。注意,nums1 的初始大小为 m + n,即有足够的空间来保存合并后的结果。你可以假设 nums1 有足够的空间(即其大小大于或等于 m + n)来保存最终的有序数组。

示例 1:

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

输出: [1,2,2,3,5,6]

说明:

  • 0 <= m, n <= 500
  • -1000 <= nums1[i], nums2[j] <= 1000

PHP 代码示例

function merge($nums1, &$m, $nums2, $n) {
    $p1 = $m - 1; // nums1的指针
    $p2 = $n - 1; // nums2的指针
    $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--;
    }

    // 更新m的值,因为nums1现在包含了m+n个元素
    $m = $m + $n;
}

// 示例用法
$nums1 = [1,2,3,0,0,0];
$m = 3;
$nums2 = [2,5,6];
$n = 3;
merge($nums1, $m, $nums2, $n);
print_r($nums1);

Python 代码示例

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] >= nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    nums1[:p2+1] = nums2[:p2+1]

# 示例用法
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

JavaScript 代码示例

function merge(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    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--;
    }
}

// 示例用法
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);

以上三种语言的代码均实现了题目要求的功能,即将两个已排序的数组合并到一个数组中,并保持其有序性。注意,在PHP示例中,$m 通过引用传递来更新其值,而在Python和JavaScript中,由于语言特性,不需要显式地更新 m 的值,因为 nums1 数组的长度在合并后自然变为 m+n

推荐面试题