合并两个有序数组

🟢 Easy · 🏷️ 数组、双指针 · LeetCode#88

📖 题目

把两个有序数组合并进 nums1，nums1 末尾已经预留好了空间。

输入	输出
nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3	[1,2,2,3,5,6]

🆕 新知识

短路求值可以用来处理边界，比 if/else 分支更紧凑：

if j < 0 or (i >= 0 and nums1[i] > nums2[j]):

j < 0 为真时，or 后面的表达式不会再求值，不用担心 nums2[j] 越界；i >= 0 这层判断同理保护了 nums1[i]。

💡 思路

如果从前往后填充，会覆盖 nums1 里还没处理的原始数据。但 nums1 末尾正好是空位，从后往前填就没有这个问题——这是这道题的关键：逆向双指针，i、j 分别指向两个数组末尾的有效元素，从 m+n-1 位置开始往前填，每次把较大的放进去。

💻 代码

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j = m - 1, n - 1
        for k in range(m + n - 1, -1, -1):
            if j < 0 or (i >= 0 and nums1[i] > nums2[j]):
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1

时间复杂度 O(m + n)，空间复杂度 O(1)。