LeetCode ＃88.合并两个有序数组

力扣 | 88.合并两个有序数组

题目截图

方法一：直接合并然后排序

利用python的切片让数组nums1的从m到m+n个 位置赋值为数组nums2的元素，然后对nums1的元素排序。

复杂度

时间复杂度：

空间复杂度：

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:m+n] = nums2
        nums1.sort()

完整测试代码

from typing import List

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:m+n] = nums2
        nums1.sort()

class main:
    a = Solution()
    num1 = [1, 2, 3, 0, 0, 0]
    m = 3
    nums2 = [2, 5, 6]
    n = 3
    b = a.merge(num1, m, nums2, n)
    print(num1)


if __name__ == '__main__':
    main()

方法二：双指针 

方法一没有利用数组为“非递减排序”的性质。可以创建一个新的数组，然后两个指针分别指向原数组nums1和nums2，相互比较大小后存入新数组，最后将新数组的元素赋值给原数组nums1。

复杂度

时间复杂度：

空间复杂度：

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.
        """
        sorted_nums = []
        p1, p2 = 0, 0
        while p1 < m or p2 < n:
            if p1 == m:
                sorted_nums.append(nums2[p2])
                p2 += 1
            elif p2 == n:
                sorted_nums.append(nums1[p1])
                p1 += 1
            elif nums1[p1] < nums2[p2]:
                sorted_nums.append(nums1[p1])
                p1 += 1
            else:
                sorted_nums.append(nums2[p2])
                p2 +=1
        nums1[:] = sorted_nums

方法三：逆向双指针

方法二需要使用临时变量sorted_nums，因为在合并数组的过程中，数组nums1中的元素可能会被新加入的元素覆盖，导致结果错误。但是数组nums1的后半段是空的，可以让指针从后往前遍历。

 

复杂度

时间复杂度：

空间复杂度：

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.
        """
        p1, p2 = m-1, n-1
        p3 = m+n-1
        while p1 >=0 or p2 >= 0:
            if p1 == -1:
                nums1[p3] = nums2[p2]
                p2 -= 1
            elif p2 == -1:
                nums1[p3] = nums1[p1]
                p1 -= 1
            elif nums1[p1] > nums2[p2]:
                nums1[p3]  = nums1[p1]
                p1 -= 1
            else:
                nums1[p3] = nums2[p2]
                p2 -=1
            p3 -= 1