原题地址

2701.png

方法一 合并+排序

合并，排序，end
简单，只需一行代码，但是时间复杂度高

python代码

  1. def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
  2.     """
  3.     Do not return anything, modify nums1 in-place instead.
  4.     """
  5.     nums1[:] = sorted(nums1[:m] + nums2)

时间复杂度O((m+n)log(m+n))

空间复杂度O(1)

方法二 双指针

思路

有一个典型的双指针问题，就是将两个有序数组合并为一个有序数组，与此题几乎一致，只不过此题又多给了一些条件和限制：

  • 两个数组中的有效元素个数为m和n，第一个数组的长度为m+n，以及需要将最终结果存储在第一个数组中。

我们大可以按照原来的思路做，采用双指针方法，将两个数组合并为一个新数组，再把新数组复制给数组1。在这里可以用一些技巧来把空间复杂度降为O(1)，也就是不用开辟新数组。

方法是：把数组1的前m个有效元素移动到最后面，然后再对数组1和数组2采用双指针方法进行合并

举例：nums1 = [1,2,3,4,0,0]; nums2 = [1,2]; m=4; n=2

  1. 先将nums1的前m个有效元素移动到后面，nums1变为[1,2,1,2,3,4]
  2. 采用双指针算法进行合并，nums1的指针p1=n，也就是指向第三个元素1,nums2的指针p2=0
  3. 然后采用经典的双指针算法进行合并排序到nums1就可以了。

python代码

  1. def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
  2.     """
  3.     Do not return anything, modify nums1 in-place instead.
  4.     """
  5.     nums1[n:] = nums1[:m]  # 将nums1的前m个元素复制到后面
  6.     p1, p2 = n, 0  # 定义双指针
  7.     p = 0
  8.     # 经典的双指针算法
  9.     while p1 < m+n and p2 < n:
  10.         if nums1[p1] < nums2[p2]:
  11.             nums1[p] = nums1[p1]
  12.             p1 += 1
  13.         else:
  14.             nums1[p] = nums2[p2]
  15.             p2 += 1
  16.         p += 1
  17.     while p1 < m+n:
  18.         nums1[p] = nums1[p1]
  19.         p += 1
  20.         p1 += 1
  21.     while p2 < n:
  22.         nums1[p] = nums2[p2]
  23.         p += 1
  24.         p2 += 1

因为是合并到nums1中，所以nums2中的元素都复制到nums1中之后，就完成任务了，所以第二个while循环其实可以去掉

时间复杂度O(m+n)

空间复杂度O(1)

方法三 双指针+从后向前

思路

与方法二相比，更加快，这次我们改进双指针算法，把指针设置为m-1, n-1，采取从后向前，由大到小的排列顺序进行，这样就省去了方法二中复制数组1的时间

python代码

  1. def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
  2.     """
  3.     Do not return anything, modify nums1 in-place instead.
  4.     """
  5.     p1, p2, p = m-1, n-1, m+n-1
  6.     while p1 >= 0 and p2 >= 0:
  7.         if nums1[p1] > nums2[p2]:
  8.             nums1[p] = nums1[p1]
  9.             p1 -= 1
  10.         else:
  11.             nums1[p] = nums2[p2]
  12.             p2 -= 1
  13.         p -= 1
  14.     while p2 >= 0:
  15.         nums1[p] = nums2[p2]
  16.         p2 -= 1
  17.         p -= 1

利用Python特性将最后一个循环去掉，局部代码如下

  1. while p1 >= 0 and p2 >= 0:
  2.     if nums1[p1] > nums2[p2]:
  3.         nums1[p] = nums1[p1]
  4.         p1 -= 1
  5.     else:
  6.         nums1[p] = nums2[p2]
  7.         p2 -= 1
  8.     p -= 1
  9. nums1[:p2+1] = nums2[:p2+1]

时空复杂度同方法二