LeetCode 88. 合并两个有序数组（易）

这道题不但可以从前往后双指针遍历，还可以从后往前三指针遍历，实现了空间复杂度为\(O(1)\)，时间复杂度为\(O(m+n)\)。

题目

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

说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 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]

考察知识点

数组、双指针

核心思想

方法一、合并加排序
直觉：先将 nums1 和 nums2 合并，然后再对其进行排序。

方法二、双指针（从前往后）

常数空间复杂度
i 指针指向 nums1 中应该插入的位置，j指针指向 nums2 中等待插入的位置，每次插入之前先回退。

m级别空间复杂度
将 nums1 复制一份 nums1_copy，遍历 nums1_copy 和 nums2，每次插入即可，不用回退。

方法三、双指针（从前后往前） 此方法最好 时间复杂度和空间复杂度都最小

791f88a8618cae4a78f15a2d2b16f94414930c813df663207c2a37b4621ea763-image.png
bac9fc86e104b5fa65f144e0604e0f4ffe4585efac12c1942b618be1c70363ca-image.png
c1ab224d0cf26c76320168efde66951bedd2d02ae89b8942e97121acf04fa36b-image.png

Python版本

  • 方法一的实现
1
2
3
4
5
6
7
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.
        """
        nums1[m:] = nums2
        nums1.sort()

时间复杂度 : \(O((n + m)\log(n + m))\)。
空间复杂度 : \(O(1)\)。
执行用时 :36 ms, 在所有 Python3 提交中击败了84.18%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.05%的用户

  • 方法二双指针（从前往后）的实现
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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.
        """
        def goBack(index):
            for i in range(len(nums1) - 1, index, -1):
                nums1[i] = nums1[i-1]

        # if m == 0:  return nums2  # nums1为空 这是一个原地算法，所以不能返回，只能修改nums1
        if m == 0:  
            nums1[:] = nums2[:]
            return
        if n == 0 and m != 0:
            nums1 = nums1[:m+1]  # nums2为空
            return
        if m == 0 and m == 0:
            nums1 = []
            return
        i = j = 0
        while m < len(nums1):
            if nums1[i] < nums2[j]:
                while nums1[i] < nums2[j] and i < m:
                    i += 1
            goBack(i)
            nums1[i] = nums2[j]
            i += 1
            j += 1
            m += 1  # 每插入一个数 m就要加一

Input = [[2,0], [0], [1], [1,2,3,0,0,0]]
Input1 = [1, 0, 1, 3]
Input2 = [[1], [1], [], [2,5,6]]
Input3 = [1, 1, 0, 3]
Answer = [[1, 2], [1], [1], [1,2,2,3,5,6]]
if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        solution.merge(Input[i], Input1[i], Input2[i], Input3[i])
        print(Input[i] == Answer[i])

时间复杂度 : \(O(n! + m)\)，goback()函数挺费时间的。
空间复杂度 : \(O(1)\)，仅使用了 i 和 j 这两个指针，也就是常数空间。

另一个双指针版本，使用了\(O(n)\)的额外空间。

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
28
29
30
31
32
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        # Make a copy of nums1.
        nums1_copy = nums1[:m] 
        nums1[:] = []

        # Two get pointers for nums1_copy and nums2.
        p1 = 0 
        p2 = 0
        
        # Compare elements from nums1_copy and nums2
        # and add the smallest one into nums1.
        while p1 < m and p2 < n: 
            if nums1_copy[p1] < nums2[p2]: 
                nums1.append(nums1_copy[p1])
                p1 += 1
            else:
                nums1.append(nums2[p2])
                p2 += 1

        # if there are still elements to add
        if p1 < m: 
            nums1[p1 + p2:] = nums1_copy[p1:]
        if p2 < n:
            nums1[p1 + p2:] = nums2[p2:]

时间复杂度 : \(O(n + m)\)。
空间复杂度 : \(O(m)\)。

  • 方法三双指针（从后往前）的实现
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(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        # two get pointers for nums1 and nums2
        p1 = m - 1
        p2 = n - 1
        # set pointer for nums1
        p = m + n - 1
        
        # while there are still elements to compare
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] =  nums1[p1]
                p1 -= 1
            p -= 1
        
        # add missing elements from nums2
        nums1[:p2 + 1] = nums2[:p2 + 1]

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

有效语法糖

1、Python在全局修改一个可变对象的方法

错误的修改方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def test(self, nums1, nums2):
        nums1 = nums2

if __name__ == "__main__":
    nums1 = [1, 100, 50, 36, 99]
    nums2 = [1, 2, 3] 
    su = Solution()
    su.test(nums1, nums2)
    print(nums1)

# Output
[1, 100, 50, 36, 99]

错误的修改方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def test(self, nums1, nums2):
        nums1 = nums2[:]

if __name__ == "__main__":
    nums1 = [1, 100, 50, 36, 99]
    nums2 = [1, 2, 3] 
    su = Solution()
    su.test(nums1, nums2)
    print(nums1)

# Output
[1, 100, 50, 36, 99]

正确的修改方法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def test(self, nums1, nums2):
        nums1[:] = nums2[:]

if __name__ == "__main__":
    nums1 = [1, 100, 50, 36, 99]
    nums2 = [1, 2, 3] 
    su = Solution()
    su.test(nums1, nums2)
    print(nums1)

# OutPut
[1, 2, 3]

参考链接

LeetCode官方题解