题目描述

[EN | CN]

给你两个有序整数数组 nums1nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

说明:

  • 初始化 nums1nums2 的元素数量分别为 mn
  • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

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

输出: [1,2,2,3,5,6]

解法 1:双指针+反向遍历

直接的做法是用两个指针分别指向两个数组的开头,然后依次遍历,如果 num2 的值比较小就插入到 nums1 对应位置,但是这样有个坏处就是 nums1 后面的元素同样会被移动,使得效率较低。

那么我们变通一下,用两个指针 i1i2 分别指向 num1num2 的末尾,我们从后往前遍历比较,这样就避免了频繁移动元素,而且也只需要原地修改数组即可。

假设数组长度分别为 $m$、$n$,那么

  • 时间复杂度为 $O(m + n)$,遍历两个数组;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i1, i2, i = m - 1, n - 1, m + n - 1
        while i1 >= 0 and i2 >= 0:
            if nums1[i1] > nums2[i2]:
                nums1[i] = nums1[i1]
                i1 -= 1
            else:
                nums1[i] = nums2[i2]
                i2 -= 1
            i -= 1
        if i2 >= 0:
            nums1[:i + 1] = nums2[:i + 1]
  • 执行用时:44 ms,在所有 Python3 提交中击败了 46.02% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 6.90% 的用户。