这个题主要是要在num1上做一个in-place的替换，也就是说，题目不想让你去添加新的参数等等。
官方solution有个挺不人道的解法是：
nums1[m:] = nums2
nums1.sort()这个确实没错，但是明显不是面试官要的，因为很明显一个非降序的数列不需要再排序一次了，且排序的时间复杂度达到了 O((n+m)log(n+m))
第二种解法就是增加一个变量，拷贝nums1前m个数，然后用two pointer。分别给nums1和nums2各自一个pointer记录index，分别比对大小。
这样时间复杂度可以达到 O(n+m).
但是空间复杂度达到了O(m)
很明显我们需要把空间复杂度降到O(1)
这道题的正确想法就是用三个pointer，nums1，nums2各自一个指向当前index的pointer而第三个指向nums1的最末尾的index。
为什么呢。
想法是，我们需要在nums1上做一个inplace替换，但是当 nums2 [ptr2] < nums1[ptr1]的时候我们不能覆盖or挪动or插入nums1，因为这样势必增加时间复杂度，但同时我们需要保存后面nums1还没有处理到的数列。
此时有且仅有一种办法就是利用nums1后面多出来的空间也就是nums1[m:]这一段。
如何运用？
我们可以从后往前找。
这样的好处是，当我们找到ptr_end < m的时候 nums1和nums2处理过的数字（ m + n - ptr_end) 一定是小于等于尚没有处理过的数字个数（ ptr1 + ptr2），不会对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.
"""
ptr1, ptr2, ptr_end = m - 1, n - 1, m + n - 1
while ptr1 >= 0 and ptr2 >= 0:
if nums1[ptr1] > nums2[ptr2]:
nums1[ptr_end] = nums1[ptr1]
ptr1 -= 1
else:
nums1[ptr_end] = nums2[ptr2]
ptr2 -= 1
ptr_end -= 1
while ptr2 >= 0:
#这个while是因为上一个ptr1 < 0后马上会跳出循环那么ptr2剩下的元素必定会是最小的几个元素，我们只需要按顺序把它们排在nums1的最前面就可以了（依然是从后向前排）
nums1[ptr_end] = nums2[ptr2]
ptr2 -= 1
ptr_end -= 1
文章评论