原文链接：go leetcode，php 代码个人原创
合并两个有序数组（Merge-Sorted-Array）
题干：
给你两个有序整数数组 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] 来源：力扣（LeetCode）
这是一题关于数组的题目。目前为止讲解数组、字符串相关的题目都会引入一个解题思路： 双指针思路。其实就是想让小伙伴们培养一个习惯：面对数组、字符串类型的题目先用 双指针思路 来捣腾捣腾。
当然这题也是引用这个思路来解题，只不过这时候的 双指针 不在指向一个数组，而是分别指向数组 num1 和 num2。
解题思路
简单粗暴的方式就是将 num1 和 num2 直接合并，再重新排序，当然不建议这么做啦。
我们仔细审一下题：题目告诉我们 num1 和 num2 是有序的，并且是从小到大排序的。那我们是不是可以从左到右依次比较 num1 和 num2 中的元素值，并将 较小的值minV 逐一存储到一个新的数组 num3 中。
但是题目有一个限制：需要将 num2 直接合并到 num1 中。这时候我们发现用从左到右的方式遍历，并将 minV 插入到 num1 中势必会产生挪动 num1 元素的操作，例如：需要在 num1 索引为 2 的位置插入 minV，那么需要将原本 索引为 2 的元素以及之后的元素都向后挪一位，空出索引为 2 的位置。成本有点大，并且也不好实现。
那么如何解决上面的问题呢？其实换成从右向左遍历就行啦。我们知道 num1 现在的长度为 m，当前最大索引记为 i ， num2 的长度为 n，当前最大索引记为 j，合并之后 num1 的长度应该是 m + n，最大索引记为 max。我们比较 num1[i] 与 num2[j] 的大小，如果 num1[i] 大于 num2[j] ，那么 num1[max] = num1[i]，max 向左移动一位，i 向左移动一位，反之 num1[max] = num2[j]，max 向左移动一位，j 向左移动一位。重复上面的操作，具体流程以及一些边界问题，查看下面的流程图：
Go 实现
func merge(nums1 []int, m int, nums2 []int, n int) {
// max 指向 nums1 与 nums2 合并之后的最后一个元素
max := m + n - 1
// 指向 num1 最后一个元素
i := m - 1
// 指向 num2 最后一个元素
j := n -1
for i >= 0 && j >= 0 {
// 从右向左比较值的大小
if nums1[i] > nums2[j] {
nums1[max] = nums1[i]
// i 向左移动
i--
} else {
nums1[max] = nums2[j]
// j 向左移动
j--
}
// max 向左移动
max --
}
// 如果 i 越界了，将 nums2 剩余的元素赋值到 num1 的 [0,m] 之间
for j >= 0 {
nums1[max] = nums2[j]
max--
j--
}
// 如果 j 越界了，其实下面这个循环可以省略。
for i >= 0 {
nums1[max] = nums1[i]
max--
i--
}
}
PHP 实现
function merge($nums1, $m, $nums2, $n) {
$i = $m - 1;
$j = $n - 1;
$max = $m + $n - 1;
while ($i >= 0 && $j >= 0) {
if ($nums1[$i] > $nums2[$j]) {
$nums1[$max] = $nums1[$i];
$i--;
} else {
$nums1[$max] = $nums2[$j];
$j--;
}
$max--;
}
while ($j >= 0) {
$nums1[$max] = $nums2[$j];
$j--;
$max--;
}
return $nums1;
}
var_dump(merge([1,2,3,0,0,0], 3, [2,5,6], 3));
最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券
