题目链接

题目描述

给你两个有序整数数组 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]

提示

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200

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

    思路

    思路1：合并后排序

    直接将 nums2 合并到 nums1 后面，然后重新排序。

    思路2：双指针

    创建新的数组，依次从两个数组中取数比较大小，然后将较小的数加入新创建的数组中。

    思路3：逆向双指针

    在思路2的解法中，如果不创建新的数组，直接从前向后加入到 nums1 中，会导致某些元素被覆盖。那有没有办法实现原地修改呢？
    考虑到 nums1 后半部分是空的，因此我们从后向前遍历，将较大的元素加入到 nums1 的尾部。
    下面来证明此做法的正确性：
    设在遍历的某一时刻，nums1 中处理过的元素个数为 n-p1-1 ，nums2 中被处理过的元素个数为 m-p2-1 ，它们都加入到了 nums1 的后半部分，而在指针 p1 的后面，有m+n-p1-1 个位置。
    我们让0088-合并两个有序数组 - 图1，得到0088-合并两个有序数组 - 图2，这是恒成立的。
    因此 p1 后面永远有足够的空间容纳处理过的元素。

    题解

    思路3：逆向双指针

    1. class Solution {
    2.  public:
    3.   void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    4.       int p1 = m - 1, p2 = n - 1;
    5.       int tail = m + n - 1;
    6.       while (p1 >= 0 || p2 >= 0) {
    7.           if (-1 == p1) {
    8.               nums1[tail--] = nums2[p2--];
    9.           } else if (-1 == p2) {
    10.               nums1[tail--] = nums1[p1--];
    11.           } else if (nums1[p1] > nums2[p2]) {
    12.               nums1[tail--] = nums1[p1--];
    13.           } else {
    14.               nums1[tail--] = nums2[p2--];
    15.           }
    16.       }
    17.   }
    18. };

    复杂度分析

    思路1：合并后排序

  • 时间复杂度：0088-合并两个有序数组 - 图3，快排的时间复杂度

  • 空间复杂度：0088-合并两个有序数组 - 图4，快排的空间复杂度

    思路2：双指针

  • 时间复杂度：0088-合并两个有序数组 - 图5

  • 空间复杂度：0088-合并两个有序数组 - 图6，需要创建新的数组

    思路3：逆向双指针

  • 时间复杂度：0088-合并两个有序数组 - 图7

  • 空间复杂度：0088-合并两个有序数组 - 图8，原地修改