题目大意
#
描述:给定两个排序后的数组 A
和 B
,以及 A
的元素数量 m
和 B
的元素数量 n
。 A
的末端有足够的缓冲空间容纳 B
。
要求:编写一个方法,将 B
合并入 A
并排序。
说明:
示例:
1
2
3
4
5
|
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
|
解题思路
#
思路 1:归并排序
#
可以利用归并排序算法的归并步骤思路。
- 使用两个指针分别表示
A
、B
正在处理的元素下标。
- 对
A
、B
进行归并操作,将结果存入新数组中。归并之后,再将所有元素赋值到数组 A
中。
思路 1:代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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.
"""
arr = []
index_A, index_B = 0, 0
while index_A < m and index_B < n:
if A[index_A] <= B[index_B]:
arr.append(A[index_A])
index_A += 1
else:
arr.append(B[index_B])
index_B += 1
while index_A < m:
arr.append(A[index_A])
index_A += 1
while index_B < n:
arr.append(B[index_B])
index_B += 1
for i in range(m + n):
A[i] = arr[i]
|
思路 1:复杂度分析
#
- 时间复杂度:$O(m + n)$。
- 空间复杂度:$O(m + n)$。