难度: Easy
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
说明:
A.length == n + m
Submission
运行时间: 19 ms
内存: 16.1 MB
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.
"""
if m==0:
for i in range(n):
A[i] = B[i]
else:
i = m-1
j = n-1
while(i>=0 and j>=0):
if A[i]>B[j]:
A[i+j+1] = A[i]
i-=1
else:
A[i+j+1] = B[j]
j-=1
for i in range(j+1):
A[i] = B[i]
Explain
此题解采用从后向前的归并排序思想。首先检查A数组中是否完全没有初始化元素（m==0），如果是这种情况，则直接将B数组的元素复制到A数组中。如果不是，定义两个指针i和j分别指向A和B中最后一个已初始化的元素。从A的最后开始，比较A[i]和B[j]的大小，将较大的元素放到A的合适位置上，即索引为i+j+1的位置，然后移动相应的指针。如果B中还有剩余的元素（当A的元素都已经被放置好，j仍大于等于0时），将这些元素复制到A数组的前部。
时间复杂度: O(m + n)
空间复杂度: O(1)
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.
\"\"\"
if m==0:
# 如果A中没有初始化的元素，直接复制B到A
for i in range(n):
A[i] = B[i]
else:
# 从后向前归并排序
i = m-1
j = n-1
while(i>=0 and j>=0):
if A[i]>B[j]:
A[i+j+1] = A[i] # 将较大的A[i]放到后面
i-=1
else:
A[i+j+1] = B[j] # 将较大的B[j]放到后面
j-=1
for i in range(j+1):
A[i] = B[i] # 处理B中剩余的元素
Explore
在这种从后向前的归并方法中，我们从A和B数组的最后一个已初始化的元素开始比较，并将比较的结果从A数组的最末尾开始填充。因为我们是从A的尾部（即空白或未使用的部分）开始填充元素，所以不会有覆盖A中尚未处理的元素的风险。即使A[i]和B[j]中的较大值是A[i]，由于我们是将A[i]移动到更后面的位置i+j+1，这个位置在所有未处理或比较的A[i]之后，因此不会影响任何尚未处理的元素。
如果A和B中的元素完全相同，这种算法不需要任何额外的步骤来处理。处理过程保持相同，由于归并的本质是比较元素大小并按顺序放置，即使所有元素相同，算法也会按照既定的步骤逐一将元素放入A的正确位置。由于我们是从后向前归并，相同的元素会被逐个复制到A的后端，不会对结果产生不良影响。
当A中没有初始化的元素时，意味着A中没有有效的数据需要保留或者比较。在这种情况下，A数组实际上是空的，只有足够的空间准备存放元素。因此，直接将B数组的元素复制到A中是最快和最直接的方法，没有必要进行任何比较。这样做可以最大限度地减少操作次数和提高效率，因为比较操作在这种情况下没有任何意义。