leetcode每日一题 python解法 3月3日
2020-03-03 本文已影响0人
Never肥宅
每日一题开始!有学python的小伙伴一起嘛
image.png
看来今天做的蛮早的,竟然击败了这么多人
难度:简单
题目内容:
给定两个排序后的数组 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的未排最大值,B的未排最大值以及未排最大值应放位置,从后往前排。
因为给定的序列A和B都是由大到小排序好的,如果直接给A在原址上排序的话,他的最后几位肯定是干净的什么也没有的,就是实例中0的部分。
依次比较A未排序数字的最后一个,也就是A未排序的最大值以及B未排序的最大值,哪个大就把它放到最大值应该去的地方,然后最大值的指针向前走一格,被拿走数字的序列的指针也往前走一格,直到排序完成。
代码
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 = n - 1 #指向B的最后一个,最大值
j = m - 1 #指向A的最后一个,最大值
last = n+m-1 #待排的最大值的位置
#从最大的,最后一个开始排
while i >= 0: #如果i是B的索引0~n-1,如果小于0 说明插入完成
if j == -1: #当A内的元素被排完,只有B没有排,就放入A中
A[0:i+1] = B[0:i+1]
break
if B[i] >= A[j]:
A[last] = B[i]
i -= 1
elif B[i] < A[j]:
A[last] = A[j]
j -= 1
last -= 1