一起学算法-88. 合并两个有序数组

一、题目88. 合并两个有序数组

LeetCode地址：[https://leetcode-cn.com/problems/merge-sorted-array/](https://leetcode-cn.com/problems/merge-sorted-array/
难度：简单

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

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

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

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10⁹ <= nums1[i], nums2[i] <= 10⁹

二、解题思路

思路一：把nums2的元素放在nums1的空位上，再进行排序。
思路二：nums1和nums2都是有规律的，并且nums2后面是空的。我们可以利用这一点，通过指针从右到左比较，直接把元素放在目标位置。

三、思路一

PHP

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer $m
     * @param Integer[] $nums2
     * @param Integer $n
     * @return NULL
     */
    function merge(&$nums1, $m, $nums2, $n) {
        if($n == 0){
            return NULL;
        }
        $j = 0;
        for($i = $m;$i < $m+$n;$i++){
            $nums1[$i] = $nums2[$j];
            $j++;
        }
        sort($nums1);
    }
}

四、思路二

c++

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int point = m-- + n-- - 1;
        while(m >= 0 && n >= 0){
            nums1[point--] = nums1[m] > nums2[n] ? nums1[m--]:nums2[n--];
        }
        while(n>=0){
            nums1[point--] = nums2[n--];
        }
    }
};

PHP

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer $m
     * @param Integer[] $nums2
     * @param Integer $n
     * @return NULL
     */
    function merge(&$nums1, $m, $nums2, $n) {
        $point = $m-- + $n-- -1;
        while($m >= 0 && $n >= 0){
            $nums1[$point--] = $nums1[$m] > $nums2[$n] ? $nums1[$m--]:$nums2[$n--];
        }
        while($n >=0){
            $nums1[$point--] = $nums2[$n--];
        }
    }
}

JavaScript

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    var r = m-- + n-- -1;
    while(m >= 0 && n >= 0){
        nums1[r--] = nums1[m] > nums2[n] ? nums1[m--]:nums2[n--];
    }
    while(n >=0){
        nums1[r--] = nums2[n--];
    }
};

五、小结

a++ 和 ++a 都是将 a 加 1，但是 a++ 返回值为 a，而++a 返回值为 a+1。