88_合并两个有序数组

类型：数组

• 88. 合并两个有序数组 💚

  https://leetcode-cn.com/problems/merge-sorted-array/

  ❓ 将有序数组 nums2 合并到有序数组 nums1 中。

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

  💡 逆向双指针

  从后向前遍历，每次取两者之中的较大者放进 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
          tail = m + n - 1
          while p1 >= 0 or p2 >= 0:
              if p1 == -1:
                  nums1[tail] = nums2[p2]
                  p2 -= 1
              elif p2 == -1:
                  nums1[tail] = nums1[p1]
                  p1 -= 1
              elif nums1[p1] > nums2[p2]:
                  nums1[tail] = nums1[p1]
                  p1 -= 1
              else:
                  nums1[tail] = nums2[p2]
                  p2 -= 1
              tail -= 1

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