1. 概述

两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

输入：

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6], n = 3

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

提示：

• -10^9 <= nums1[i], nums2[i] <= 10^9

• nums1.length == m + n

• nums2.length == n

2. 解题

<?php
class Solution
{
    /**
     * @param Integer[] $nums1
     * @param Integer $m
     * @param Integer[] $nums2
     * @param Integer $n
     * @return NULL
     */
    public function merge(&$nums1, $m, $nums2, $n)
    {
        $newM = $m;
        $newJ = 0;
        for ($i = 0; $i < $m; $i++) {
            for ($j = $newJ; $j < $n; $j++) {
                if ($nums1[$i] >= $nums2[$j]) {
                    $newJ = $j + 1;
                    $newM++;
                    $this->moveRightOne($nums1, $i);
                    $nums1[$i] = $nums2[$j];
                } else {
                    break;
                }
            }
        }
        if ($newJ <= $n) {
            for ($k = $newJ; $k <= $n; $k++) {
                if (!isset($nums2[$k])) break;
                $nums1[$newM++] = $nums2[$k];
            }
        }
        return;
    }
    // $nums1 从下标 $startIndex 开始逐个遍历向右移动一格
    private function moveRightOne(&$nums1, $startIndex)
    {
        for ($i = count($nums1) - 2; $i >= $startIndex; $i--) {
            $nums1[$i + 1] = $nums1[$i];
        }
        $nums1[$startIndex] = 0;
    }
}
$nums1 = [1, 2, 3, 0, 0, 0];
$m = 3;
$nums2 = [2, 5, 6];
$n = 3;
$cls = new Solution();
$ret = $cls->merge($nums1, $m, $nums2, $n);
print_r($nums1);