PHP7.3实现合并两个有序数组，PHP算法题解-php教程-PHP中文网

LeetCode 88题要求原地合并两个有序数组，必须从后往前双指针归并：因nums1后n位为空闲空间，从前向后会覆盖未处理元素；而从k=m+n−1开始填最大值，可避免读写冲突，实现O(m+n)时间、O(1)空间。

php7.3实现合并两个有序数组，php算法题解

PHP 7.3 中实现“合并两个有序数组”这道题，核心不是简单拼接，而是利用已有序特性做 原地归并，时间复杂度 O(m+n)，空间复杂度 O(1)。它和 LeetCode 88 题逻辑一致：给定数组 nums1（长度为 m+n，后 n 位为占位 0），nums2（长度为 n），要求将 nums2 合并入 nums1 并保持非递减顺序。

为什么必须从后往前合并？

因为 nums1 的有效数据只占前 m 位，后 n 位是空闲空间。若从前向后归并，可能覆盖 nums1 中尚未处理的元素；而从后往前，每次把当前最大值放到 nums1[k]（k 从 m+n−1 开始递减），完全避开读写冲突。

指针 i = m − 1 指向 nums1 最后一个有效数
指针 j = n − 1 指向 nums2 最后一个数
指针 k = m + n − 1 指向 nums1 合并后末尾位置

完整 PHP 7.3 兼容实现

以下代码严格遵循原地、无额外数组、兼容空输入（m=0 或 n=0）：

function merge(&$nums1, int $m, array $nums2, int $n): void
{
    $i = $m - 1;
    $j = $n - 1;
    $k = $m + $n - 1;
<pre class="brush:php;toolbar:false;">// 双指针从后往前比较，填入 nums1[k]
while ($i >= 0 && $j >= 0) {
    if ($nums1[$i] > $nums2[$j]) {
        $nums1[$k--] = $nums1[$i--];
    } else {
        $nums1[$k--] = $nums2[$j--];
    }
}

// 若 nums2 还剩元素（nums1 已耗尽），全部拷入 nums1 前部
while ($j >= 0) {
    $nums1[$k--] = $nums2[$j--];
}

// 若 nums1 还剩元素，无需操作——它们已在正确位置

}

注：PHP 7.3 支持严格类型声明（如 int $m），函数签名中使用 &$nums1 确保原地修改生效。