题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

算法思路

这个题目如果能开一个额外的$O(m+n)$的空间的话，非常简单，参考”合并两个升序链表“这种题就可以了，但是要想做的”优雅“一点，肯定是希望常数空间就解决，这个地方一开始就看出来是双指针，但是我从前往后遍历看了很多遍都不知道应该怎么处理，因为从前往后的话，就需要升序处理，然而当i<m时，nums1[i]是有元素的，怎么处理这个元素是个很麻烦的问题，最后想了半天也没有想出一种时间复杂度$O(m+n)$，空间复杂度$O(1)$的做法。然后去看了评论区一个大神的题解，这个思路真的就是，一点变化就能让解题过程千差万别，他采用了倒序遍历的方法，因为如果倒序的话，nums1[i]这个位置就没有元素了，这时候只需要降序排列就可以，优先选择nums1[j],nums2[k]中较大的元素，放在nums1[i]那个位置即可。截取一张该大神的图像，就可以大致理解了。

img

我第一遍只看了他的思路，没有看代码，然后去尝试自己写，于是就写出了屎山代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m + n - 1;
        int j = m - 1;
        int k = n - 1;
        while (i >= 0) {
            if (j < 0) {
                while (k >= 0) {
                    nums1[i] = nums2[k];
                    i--; k--;
                }
            }
            if (k < 0) {
                break;
            }
            if (nums1[j] >= nums2[k]) {
                nums1[i] = nums1[j];
                i--; j--;
            }
            else {
                nums1[i] = nums2[k];
                i--; k--;
            }
        }
    }
};

虽然容易理解吧，但是确实长了点，然后看看大神题解：

1
2
3
4
5
6
7
8
9
10
11
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = nums1.size() - 1;
    m--;
    n--;
    while (n >= 0) {
        while (m >= 0 && nums1[m] > nums2[n]) {
            swap(nums1[i--], nums1[m--]);
        }
        swap(nums1[i--], nums2[n--]);
    }
}