Index of nth biggest item in Python list [closed]
I can't edit or sort the list. How ca开发者_如何学Cn I get that index?
The heapq module provides a nlargest function that efficiently finds the n largest elements of a list:
>>> from heapq import nlargest
>>> items = [100, 300, 200, 400]
>>> indexes = [0, 1, 2, 3]
>>> nlargest(2, indexes, key=lambda i: items[i])
[3, 1]
What you've got is already O(n) in complexity (max
is O(n), as is index()
, IIRC). So while you could technically just remove the largest if it's not appropriate and try again, you're starting to get into bubblesort territory in terms of big-O. How many items are typically on the list?
One option is QuickSelect, which is basically a reduced QuickSort, but honestly just sorting the list up front is not going to be much slower than what you've got already.
You can use the sorted() function to return a new sorted list if you don't want to change the ordering of the original list.
精彩评论