解题思路
解法一：直接合并后排序（不推荐）
复杂度分析
时间复杂度：O((m+n)log(m+n))，排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。
空间复杂度：O(log(m+n))，排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。
解法二：双指针法
分别为两个数组设置一个指针pa与pb，来作为队列的头指针。如果数组A的第一个数字比数组B的第一个数字小，则把它放入新的数组中；反之，则把数组B的第一个数字放入新的数组中。然后继续比较A、B两个数组剩余的部分，合并的步骤和之前的步骤是一样的。此法需要单独开辟一个新的数组C，用来存储A、B合并排序后的结果。
步骤：
1)开辟一个新的数组C，并将pa、pb指向A、B数组的第一个元素，pa = 0，pb = 0；
2)进入循环，当pa或者pb还没有到达各自数组末端时，即 while(pa<m or pb<n)，执行以下操作：
2.1)如果pa先到达A的末端，则将B数组剩余部分元素逐个加入新数组C，pb++；
2.2)如果pb先到达B的末端，则将A数组剩余部分元素逐个加入新数组C，pa++；
2.3)如果pa和pb都没到达数组末端，则比较相互元素，小的加入新数组C
2.3.1)A数组元素小，将A中元素加入，并移到A数组下一个元素，pa++；
2.3.2)B数组元素小，将B中元素加入，并移到B数组下一个元素，pb++；
3)结束循环，返回新数组C，并把C赋值给A。
复杂度分析
时间复杂度：O(m+n)，指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(m+n)，需要建立长度为 m+n 的中间数组 。
解法三：逆向双指针法
解法二中需要额外开辟一个新的数组，是因为如果直接合并到数组 A 中，A 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 A 中的元素呢？观察可知，A 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 A 的最后面。
步骤：
1)将pa和pb分别指向A、B数组的最后一个元素，pa = m - 1，pb = n - 1，另外再创建一个尾指针指向A数组尾部 tail = m + n - 1；
2)进入循环，当pa或者pb还没有到达各自数组首端时，即 while(pa>=0 or pb>=0)，执行以下操作：
2.1)如果pa先到达A的首段，则将B数组剩余部分元素逐个加入，pb--；
2.2)如果pb先到达B的首段，则将A数组剩余部分元素逐个加入，pa--；
2.3)如果pa和pb都没到达数组末端，则比较相互元素，大的加入
2.3.1)A数组元素大，将A中元素加入，并移到A数组前一个元素，pa--；
2.3.2)B数组元素大，将B中元素加入，并移到B数组前一个元素，pb--；
2.4)尾指针前移，tail--；
3)结束循环，返回数组A。
注：此法只针对于A数组尾部有足够缓冲空间可以容纳B数组。
复杂度分析
时间复杂度：O(m+n)，指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(1)，直接对数组 A 原地修改，不需要额外空间。
代码
解法一：直接合并后排序
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
A[m:] = B
A.sort()
解法二：双指针法
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
pa, pb = 0, 0
C = []
while pa < m or pb < n:
if pa == m:
C.append(B[pb])
pb += 1
elif pb == n:
C.append(A[pa])
pa += 1
elif A[pa] < B[pb]:
C.append(A[pa])
pa += 1
else:
C.append(B[pb])
pb += 1
A[:] = C
解法三：逆向双指针法
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
pa, pb = m-1, n-1
tail = m + n -1
while pa >= 0 or pb >= 0:
if pa == -1:
A[tail] = B[pb]
pb -= 1
elif pb == -1:
A[tail] = A[pa]
pa -= 1
elif A[pa] > B[pb]:
A[tail] = A[pa]
pa -= 1
else:
A[tail] = B[pb]
pb -= 1
tail -= 1
网友评论