python - 什么是 O(n) 算法将两个等长列表按顺序配对？

Question

假设我在 Python 中有两个等长的无序列表:

a = [5, 2, 3, 1, 4]
b = ['d', 'b', 'a', 'c', 'e']

是否有 O(n) 的就地算法来获得以下结果？

[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')]

Answer 1

您正在寻找 zip和 sorted内置函数。

r = zip(sorted(a), sorted(b))

zip 获取两个可迭代对象并将它们按顺序配对(因此如果列表未排序，您将得到 (5, 'd') 作为您的第一个元组)，并且任何多余的值似乎都被截断/忽略了(因为它们无法配对)。

sorted，我上次查看代码库时，根据您给它的列表的大小使用不同的排序算法 - 它应该执行大约 O(n*log(n )). 没有一种实用的排序方法可以为您提供 O(n) 的性能，因为您仍然必须将单个值与其他值进行比较，一些时间。

如果您想要就地排序，可以使用 list.sort() 函数，它会执行就地排序。这会将语法更改为以下内容:

a.sort()
b.sort()
r = zip(a, b)