题目：合并两个有序数组

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

说明:

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

示例:

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

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

来源：力扣（LeetCode）第88题

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

分析：

• 从后往前放元素，就能解开了。

代码：

• Python

  class Solution:
  def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
      p1 = m - 1  # num1的指针
      p2 = n - 1  # num2的指针
      p = m + n - 1  # num1存放答案的指针
      while p1 >= 0 and p2 >= 0:  # 将两者大的值放进去。
          if nums1[p1] > nums2[p2]:
              nums1[p] = nums1[p1]
              p1 -= 1
          else:
              nums1[p] = nums2[p2]
              p2 -= 1
          p -= 1
      nums1[:p2+1] = nums2[:p2+1]  # 最后将nums2中还没放完的元素放进去。
  

• Java

  class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
      int p1 = m - 1;
      int p2 = n - 1;
      int p = m + n - 1;
      while (p1 >= 0 && p2 >= 0) {
          if (nums1[p1] > nums2[p2]) {
              nums1[p--] = nums1[p1--];
          } else {
              nums1[p--] = nums2[p2--];
          }
      }
      while (p2 >= 0) nums1[p--] = nums2[p2--];
  }
  }
  

  复杂度分析：

• 时间复杂度：O(n+m)

• 空间复杂度：O(1)