题目描述

合并两个有序数组是一个常见的算法问题，具体描述如下：

给定两个已排序的整数数组 nums1 和 m，nums2 和 n，其中 m 是 nums1 的长度，n 是 nums2 的长度。你需要将 nums2 合并到 nums1 中，使得 nums1 的前 m + n 个元素包含合并后的有序数组。注意，nums1 的初始长度为 m，且 nums1 有足够的空间来存储合并后的数组，即 nums1 的大小至少为 m + n。你可以假设 nums1 和 nums2 是按非递减顺序排列的。

注意： 请不要使用额外的数组空间来合并这两个数组，你只能在 nums1 上就地修改，并且不能改变 nums1 和 nums2 的原始长度（即 nums1 的原始长度为 m，nums2 的原始长度为 n）。

示例

假设 nums1 = [1,2,3,0,0,0]，m = 3，nums2 = [2,5,6]，n = 3，则合并后的 nums1 应该为 [1,2,2,3,5,6]。

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 += $n;
}

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

Python 代码示例

def merge(nums1, m, nums2, n):
    p1, p2 = m - 1, n - 1
    p = 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

    # 如果 nums2 还有剩余元素，将它们复制到 nums1
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

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

这些示例展示了如何在 PHP 和 Python 中实现合并两个有序数组的问题，遵循了题目要求，并且没有使用额外的数组空间。