开发者

Index of nth biggest item in Python list [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 12 years ago.

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜