leetcode-数组-88-合并两个有序数组

题目描述（难度：简单）

• 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明

• 初始化 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]

解题思路

• 暴力法：从前往后一个个对比，将 nums2 中的数逐个插入 nums1 中
• 排序法：合并两个数组再排序，API 直接完成
• 递减法：从后往前对比，将较大值放入 nums1 的空值位置

代码

• 暴力法

    /**
  * 暴力法
  * @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) {
    let i = 0,
        j = 0
    // 去0
    nums1.splice(m, n)
    // 如果 nums1 没值，直接把 nums2 放入
    if (!m) {
        nums1.splice(0, 0, ...nums2.splice(j));
        return nums1;
    }
    while(i < m || j < n) {
        // 对比将小值插入 nums1 中
        if (nums2[j] <= nums1[i]) {
            nums1.splice(i, 0, nums2[j]);
            j++;
            m++;
        } else {
            i++;
        }
        // 当 i 等于 m 代表从 j 开始的 nums2 元素都比 nums1 大，直接插入
        if (i === m) {
            nums1.splice(i, 0, ...nums2.splice(j));
            break;
        }
    }
    return nums1;
  };

• 排序法

    function merge(nums1, m, nums2, n) {
        for (var i = 0; i < nums2.length; i++) nums1[m + i] = nums2[i];
        nums1.sort(function (a, b) {
            return a - b
        })
        return nums1;
    };

• 递减法

    /**
    * 递减法
    * @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) {
        let p = m-- + n-- - 1; // nums1 总长度
        while (m >= 0 && n >= 0) {
            // 对比有序数组中的最大值，结果为所有元素最大值，放入 nums1 数组最后
            nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        // n 大于零，即有比原 nums1 所有元素小的值，直接将其放入 nums1
        while (n >= 0) {
            nums1[p--] = nums2[n--];
        }
        return nums1;
    }