Python中的一阶统计量

Question

给定一个n可比较元素的列表（比如数字或字符串），找到第i个有序元素的最佳算法需要O(n)时间。在

Python是否在本机实现O(n)列表、dict、set等的时序统计信息。。。？在

Answer 1

Python提到的数据结构都没有实现i阶统计算法。在

事实上，对于字典和集合来说，这可能没有多大意义，因为它们都没有假设元素的顺序。对于列表，实现selection algorithm应该不难，它提供O（n）运行时间。在

Answer 2

如果i<；<；n您可以查看http://docs.python.org/library/heapq.html#heapq.nlargest和{a2}（它们不能解决您的问题，但是比排序和获取第i个元素更快）。在

Answer 3

这不是一个原生的解决方案，但是您可以使用NumPy的partition来查找O（n）时间内列表的k阶统计量。在

import numpy as np
x = [2, 4, 0, 3, 1]
k = 2
print('The k-th order statistic is:', np.partition(np.asarray(x), k)[k])

编辑：这假设索引为零，即上面的“零阶统计”是0。在