Python列表中第n大元素的索引

Question

我无法编辑或排序这个列表。我该如何获取那个索引呢？

Answer 1

你现在的做法复杂度已经是O(n)了（max的复杂度是O(n)，index()也是，没记错的话）。所以虽然你可以技术上去掉最大值再试一次，但这样做的复杂度就有点像冒泡排序了。通常这个列表里有多少个项目呢？

一个选择是QuickSelect，这基本上是简化版的快速排序，但老实说，直接先把列表排序也不会比你现在的做法慢多少。

如果你不想改变原始列表的顺序，可以使用sorted()函数来返回一个新的已排序列表。

Answer 2

heapq模块提供了一个叫做nlargest的功能，可以快速找到列表中最大的n个元素：

>>> from heapq import nlargest
>>> items = [100, 300, 200, 400]
>>> indexes = [0, 1, 2, 3]
>>> nlargest(2, indexes, key=lambda i: items[i])
[3, 1]