各位题友大家好！今天是 @负雪明烛 坚持日更的第 71 天。今天力扣上的每日一题是「88. 合并两个有序数组」。

解题思路

本题重点：
- 两个数组有序；
- 合并结果放到 nums1 中

注意题目给出的数组的方式：nums1 中本身有效的数字是前 m 位，nums1 的长度是 m + n，因此正好可以放下 nums1[0:m] + nums2[0:n]。

合并两个有序数组，我们第一反应肯定是想到了归并排序。归并排序是把两个有序的数组合并、放到另外一个数组中。所以空间复杂度是 $O(M + N)$ 的。

由于本题给出的 nums1 是能够保证其长度能够放得下 m + n 个元素的，所以可以直接把合并的结果放到 nums1 中。

思路一：如果两个数组从开头向结尾（数字从小到大）进行比较，那么每次把比较之后的数字放置到 nums1 中的前面，则需要把 nums1 中第 k 个位置后面的元素向后移动。移动次数比较多。
- 思路二：如果两个数组从结尾向开头（数字从大到小）进行比较，那么每次把比较之后的数字放置到 nums1 中的后面，由于后面的数字本身就是提供出来的多余的位置，都是 0，因此不需要对 nums1 进行移动。

显然思路二更好。

从后向前进行比较

确定了主要的思路之后，实现起来其实很简单。

当 m > 0 并且 n > 0 时，从后向前比较 $num1[m - 1]$ 和 $nums2[n - 1]$ ：
- 如果是 $nums1[m - 1]$ 大，则把 $nums1[m - 1]$放到 $num1$ 的第 $m + n - 1$ 位置，并让 $m -= 1$。
- 如果是 $nums1[n - 1]$ 大，则把 $nums2[n - 1]$ 放到 $num1$ 的第 $m + n - 1$ 位置，并让 $n -= 1$。
2. 当上面的遍历条件结束的时候，此时 m 和 n 至少有一个为 0。
- 当 m == 0 时，说明 num1 的数字恰好用完了，此时 nums2 可能还剩元素，需要复制到 nums1 的头部；
- 当 n == 0 时，说明 num2 的数字恰好用完了，此时 nums1 可能还剩元素，由于剩余的这些元素一定是 nums1 和 nums2 中最小的元素，所以不用动，直接留在原地就行。

代码

写了 Python, C++, Java 三种语言的代码。

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        k = m + n - 1
        while m > 0 and n > 0:
            if nums1[m - 1] > nums2[n - 1]:
                nums1[k] = nums1[m - 1]
                m -= 1
            else:
                nums1[k] = nums2[n - 1]
                n -= 1
            k -= 1
        nums1[:n] = nums2[:n]

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

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1;
        while (m > 0 && n > 0) {
            if (nums1[m - 1] > nums2[n - 1]) {
                nums1[k] = nums1[m - 1];
                m --;
            } else {
                nums1[k] = nums2[n - 1];
                n --;
            }
            k --;
        }
        for (int i = 0; i < n; ++i) {
            nums1[i] = nums2[i];
        }
    }
}

时间复杂度：$O(M + N)$
空间复杂度：$O(1)$

刷题心得

由于归并排序的思路惯性，我们已经习惯了从前向后比较。这个题帮助了我们打破惯性。

参考资料：
88. Merge Sorted Array

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】88. 合并两个有序数组

解题思路

从后向前进行比较

代码

刷题心得