题目链接：https://leetcode.cn/problems/merge-sorted-array/
题目描述：
分析：首先观察题目的关键词，非递减顺序，两个整数分别表示元素数目（不是数组长度），现在希望合并两个数组，让合并后的数组同样非递减顺序排列。
解法一：直接解法
最简单的解法就是将两个数组合并然后对整个数组进行排序。
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((m+n))log((m+n))，排序序列长度为m+n，套用快速排序的时间复杂度就行，平均情况为O((m+m))log((m+n))
- 空间复杂度：O(log(m+n))，排序序列长度为m+n，套用快速排序的空间复杂度就可以，平均情况为O(log(m+n))
解法二：双指针
方法一没有利用数组已经被排序的性质，为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。
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 = [] p1, p2 = 0, 0 while p1 < m or p2 < n: if p1 == m: sorted.append(nums2[p2]) p2 += 1 elif p2 == n: sorted.append(nums1[p1]) p1 += 1 elif nums1[p1] < nums2[p2]: sorted.append(nums1[p1]) p1 += 1 else: sorted.append(nums2[p2]) p2 += 1 nums1[:] = sorted
在这段代码中，`nums1[:] = sorted` 使用切片赋值的方式将 `nums1` 的内容替换为 `sorted` 中的元素。这种方式是为了确保原地修改 `nums1` 的内容，而不是简单地将 `nums1` 的引用指向另一个列表 `sorted`。
当使用 `nums1 = sorted` 进行赋值时，实际上是将 `nums1` 的引用指向了 `sorted`，而不是修改 `nums1` 所指向的实际对象。这样做的话，`nums1` 将不再引用原来的数组，而是引用了一个新的数组 `sorted`，并且原来的 `nums1` 数组将无法被修改。
为了确保在原地修改 `nums1`，我们使用切片赋值 `nums1[:] = sorted`。这样做会修改 `nums1` 数组的元素值，并保持引用不变。切片赋值操作会将 `sorted` 中的元素逐个复制到 `nums1` 中，从而实现在原地修改 `nums1` 的目的。
需要注意的是，使用切片赋值 `nums1[:] = sorted` 只适用于可变的序列类型（如列表），对于不可变的序列类型（如字符串），则不能使用这种方式进行修改。
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 = [] p1, p2 = 0, 0 while p1 < m or p2 < n: if p1 == m: sorted.extend(nums2[p2:n]) break elif p2 == n: sorted.extend(nums1[p1:m]) break elif nums1[p1] < nums2[p2]: sorted.append(nums1[p1]) p1 += 1 else: sorted.append(nums2[p2]) p2 += 1 nums1[:] = sorted
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. """ result = [] p1, p2 = 0, 0 while p1 < m and p2 < n: if nums1[p1] < nums2[p2]: result.append(nums1[p1]) p1 += 1 else: result.append(nums2[p2]) p2 += 1 if p1 < m: result.extend(nums1[p1:m]) if p2 < n: result.extend(nums2[p2:n]) nums1[:] = result
注意：如果想要直接追加剩余的元素，不要忘记nums1后边有元素0，直接nums1[p1:]会导致错误。
复杂度分析：
- 时间复杂度：O(m+n)，指针移动单调递增，最多移动m+n次，因此时间复杂度为O(m+n)
- 空间复杂度：O(m+n)，需要建立长度为m+n的中间数组sorted
方法三：逆向双指针
方法二中，之所以要使用临时变量，是因为如果直接合并到数组nums1中，nums1中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖nums1中的元素呢？观察可知，nums1的后半部分是空的，可以直接覆盖不会影响结果，因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进nums1的最后边。
严格来说，在此遍历过程中的任意一个时刻，nums1数组中有m-p1-1个元素被放入nums1的后半部，nums2数组中有n-p2-1个元素被放入nums1的后半部，而在指针p1的后面，nums1数组有m+n-p1-1个位置。由于m+n-p1-1>=m-p1-1+n-p2-1，等价于p2>=-1永远成立，因此p1后面的位置永远足够容纳被插入的元素，不会产生p1的元素被覆盖的情况。
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
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 = m-1 p2 = n-1 while p1 >= 0 or p2 >= 0: if p1 < 0: nums1[:p2+1] = nums2[:p2+1] break elif p2 < 0: break elif nums1[p1] < nums2[p2]: nums1[p1 + p2 + 1] = nums2[p2] p2 -= 1 else: nums1[p1 + p2 + 1] = nums1[p1] p1 -= 1
复杂度分析：
- 时间复杂度：O(m+n)，指针移动单调递减，最多移动m+n次，因此时间复杂度为O(m+n)
- 空间复杂度：O(1)，直接对数组nums1进行修改，不需要额外的空间