今天遇到一个面试题，经朋友提点实际上是排序算法中 merge sort 的 merge 步，蛋疼实现了一下两个做法，一个是利用堆栈，另一个尝试用角标。
角标的判定真的很恶心，也如朋友所说，很容易越界没判断好。
参考资料：
- alrightchiu.github.io/SecondRound…
import copy
def merge1(x:list, y:list, debug=False):
"""使用堆栈"""
new_ = list()
x_ = copy.copy(x)
y_ = copy.copy(y)
while x_ and y_:
if x_[-1] > y_[-1]:
new_.append(x_.pop(-1))
elif x_[-1] == y_[-1]:
new_.append(x_.pop(-1))
y_.pop(-1)
else:
new_.append(y_.pop(-1))
new_ = new_ + x_ + y_
return new_
def merge2(x:list, y:list, debug=False):
"""单纯使用角标"""
new_ = list()
x = copy.copy(x)
y = copy.copy(y)
idx_x = len(x) - 1
idx_y = len(y) - 1
while True:
if debug:
print(idx_x, idx_y)
if idx_x >= 0 and idx_y >= 0:
x_ = x[idx_x]
y_ = y[idx_y]
else:
break
if x_ > y_:
new_.append(x_)
idx_x -= 1
elif x_ == y_:
new_.append(x_)
idx_x -= 1
idx_y -= 1
else:
new_.append(y_)
idx_y -= 1
# 由 break 的条件是角标出界了，即小于零，即两个角标存在一个是 -1， 一个是正整数，只有后者能通过 slice 取到值即为 tail
tail = y[:idx_y+1] or x[:idx_x+1]
new_.extend(tail)
return new_
a = [i for i in range(3, 12, 2)]
b = [i for i in range(1, 30, 10)]
m1 = merge1(a, b)
m2 = merge2(a, b)
assert m1 == m2, print("m1:",m1, "\nm2:",m2, "\na:",a, "\nb:",b)
复制代码