题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定两个排序后的数组 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
题目思考
- 如何放置排序后的数字才不会覆盖 A 原始数字?
解决方案
思路
- 分析题目, 要合并两个排序的数组, 首先想到的就是归并排序, 这道题也可以采用类似的思路, 稍作改动即可
- 由于 A 的末端有足够的缓冲空间容纳 B, 所以我们可以预先得到排序后的数组长度以及其最后一个下标 k (即 m+n-1)
- 然后维护当前 A 和 B 的下标 i 和 j, 也初始化为各自的最后一个下标 (m-1 和 n-1)
- 最后从后向前遍历并归并即可, 注意由于是从后向前遍历, 所以要使用两者之中的较大者作为下标 k 处的数字
- 下面的代码就对应了上面的整个过程, 并且有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(M+N): 需要遍历数组 A 和 B 的所有数字各一次 - 空间复杂度
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.
"""
# 多指针+从后向前归并排序
# i是当前A数组的下标; j是当前B数组的下标; k是合并后的数组下标
# 分别将其初始化为最后一个元素, 然后从后向前遍历, 从而避免更新k时覆盖尚未遍历的A数组元素
i, j, k = m - 1, n - 1, m + n - 1
for k in range(m + n)[::-1]:
if i < 0 or j >= 0 and A[i] <= B[j]:
# A数组已经遍历完毕, 或者当前B[j]更大, 使用B[j]
A[k] = B[j]
j -= 1
else:
# 否则说明B数组已经遍历完毕, 或者当前A[i]更大, 使用A[i]
A[k] = A[i]
i -= 1 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号