什么是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)