Python中的第i个顺序统计量

Question

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

Python是否本地实现了O(n)时间复杂度的排序统计算法，适用于列表、字典、集合等？

- Randomblue

---

希望能得到那位投反对票和关闭投票者的评论。 - Randomblue

Answer 1

Python中提到的数据结构都没有原生实现第i个顺序统计算法。

实际上，对于字典和集合来说，这可能没有太多意义，因为两者都不会对其元素的顺序做出任何假设。对于列表来说，实现选择算法应该不难，这可以提供O(n)的运行时间。

- Óscar López

Answer 2

这并不是一种本地解决方案，但您可以使用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。

- Garrett

---

这不是准确的。在分区后，您需要找到最大值。因此，可以使用以下代码：np.partition(np.asarray(x), k)[:k].max() - piRSquared

@piRSquared，谢谢。我认为你把它解释成了从1开始计数，所以我现在已经澄清了这一点。 - Garrett

我的观点是np.partition不是排序。这就是它的优点所在，也是为什么它更好。话虽如此，因为它没有排序，不能保证第k个顺序统计量在第k个位置上。我不是指基于零或一的索引。我指的是有时您的解决方案会产生错误的答案。假设我想从0到36的随机洗牌整数集中获取第5个顺序统计量。您的答案在这里使用我的示例生成1：np.random.seed(0); np.partition(np.random.permutation(np.arange(37)), 5)[4]。答案应该是4。 - piRSquared

为了纠正这个问题，您需要找到前k个元素中的最大值。np.random.seed(0); np.partition(np.random.permutation(np.arange(37)), 5)[:5].max() - piRSquared

在你的例子中，第0个顺序统计量为0，第5个顺序统计量为5。尝试运行以下代码：np.partition(np.random.permutation(np.arange(37)), 5)[5]，你将得到正确的答案5。你是正确的，np.partition不会排序，但它确保数字5在第5个位置上。 - Garrett

Answer 3

如果i << n，你可以看一下http://docs.python.org/library/heapq.html#heapq.nlargest和http://docs.python.org/library/heapq.html#heapq.nsmallest（它们不能解决你的问题，但比排序并获取第i个元素更快）。

- user109839