「本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！」

题目描述：

LeetCode 地址

标签：数组

难度：简单

描述：

给你两个有序整数数组 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
• 109 <= nums1[i], nums2[i] <= 109

题解

题目理解

1. 考察点：双指针算法
2. 注意：nums1 已存在 m + n 个空间了，需要去除多余的 n 个空间

解法一：暴力破解法

解题思路

1. 核心思路：将两个数组合并，再排序。
2. 注意：nums1 已存在 m + n 个空间了，需要去除多余的 n 个空间

代码

/**
 * @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) {
    nums1.splice(m, n, ...nums2);
    nums1.sort((a, b) => a - b);
};
复制代码

算法分析

1. 时间复杂度：O(m+n)
2. 空间复杂度：O(1)

解法二：双指针法(正向)

解题思路

核心思路：指针从前 –> 后
注意：边界条件

代码

/**
 * @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 result = [];
   let p1 = 0, p2 = 0;
   // 错误写法：p1 <= m && p2 <= n
   while(p1 < m && p2 < n) {
       if (nums1[p1] <= nums2[p2]) {
           result.push(nums1[p1]);
           p1++;
       } else {
           result.push(nums2[p2]);
           p2++;
       }
   }
   
   while(p1 < m && p2 >= n) {
       result.push(nums1[p1]);
       p1++;
   }
   while(p2 < n && p1 >= m) {
       result.push(nums2[p2]);
       p2++;
   }
   for(let i = 0; i < m+n; i++) {
       nums1[i] = result[i];
   }
};
复制代码

/**
 * @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 result = new Array(m + n).fill(0);
   let p1 = 0, p2 = 0, k = 0;
   // 错误写法：p1 <= m && p2 <= n
   while(p1 < m && p2 < n) {
       if (nums1[p1] <= nums2[p2]) {
           result[k] = nums1[p1];
           p1++;
       } else {
           result[k] = nums2[p2];
           p2++;
       }
       k++;
   }
   
   while(p1 < m && p2 >= n) {
       result[k] = nums1[p1];
       k++;
       p1++;
   }
   while(p2 < n && p1 >= m) {
       result[k] = nums2[p2];
       k++;
       p2++;
   }
   for(let i = 0; i < m+n; i++) {
       nums1[i] = result[i];
   }
};
复制代码

算法分析

1. 空间复杂度：O(m+n)
2. 时间复杂度：O(m+n): 都需要一个（m+n）的中间数组

解法三：双指针法（逆向）

解题思路

1. 核心思路：指针从后 –> 前

代码

/**
 * @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 p1 = m - 1, p2 = n - 1, k = m + n - 1;
    while(p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[k] = nums1[p1];
            p1--;
        } else {
            nums1[k] = nums2[p2];
            p2--;
        }
        k--;
    }
    while(p2 >= 0 && p1 < 0) {
        nums1[k] = nums2[p2];
        p2--;
        k--;
    }
}
复制代码

算法分析

1. 时间复杂度：O(m+n)
2. 空间复杂度：O(1): 直接对数组原地修改不需要额外的空间

总结

1. 合并两个有序数组，最简单的就是先合并数组，然后排序，需要注意的就是 nums1 的空间问题。
2. 双指针算法：
   • 双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。
   • 利用两个指针遍历数组（链表），左右指针相向前进或同向前进，在遍历过程中根据某种限制条件进行筛选，通常可以把时间复杂度降低至O(n)