Index du nième élément le plus important dans la liste Python

Question

Je ne peux pas éditer ou trier la liste. Comment puis-je obtenir cet indice?

Answer 1

Le module heapq fournit une fonction nlargest qui trouve efficacement les éléments n plus d'une liste:

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

Answer 2

Qu'est-ce que vous avez est déjà O (n) en complexité (max est O (n), comme index(), IIRC). Donc, tandis que pourrait techniquement enlever simplement le plus grand si ce n'est pas approprié et essayez à nouveau, vous commencez à entrer dans le territoire de bubbleort en termes de big-O. Combien d'éléments sont généralement sur la liste?

Une option est QuickSelect, ce qui est fondamentalement un QuickSort réduit, mais honnêtement, juste trier la liste à l'avance ne sera pas beaucoup plus lent que ce que vous avez déjà.

Vous pouvez utiliser la fonction sorted() pour renvoyer une nouvelle liste triée si vous ne souhaitez pas modifier l'ordre de la liste d'origine.