J'ai la liste qui, comme suit Je veux obtenir tous les index de la valeur maximale. Besoin d'une solution efficace. La sortie sera la suivante. P> m = max(input_list)
output = [i for i, j in enumerate(a) if j == m]
5 Réponses :
Vous pouvez utiliser sortie: numpy numpy ( NUMPY NUMPY Les tableaux sont très rapide ):
Utilisez A pour boucle pour ici, vous avez le Exemple en direct O (n) et itération juste une fois sur la résolution de la liste:
Je ne sais pas si ceci est différent, ce que l'OP est déjà, mais semble ajouter plus de verbosité à la solution!
@Deveshkumarsingh, il est verbeux dans le but d'expliquer toutes les conditions. Et c'est la seule réponse qui la résout dans une itération sur les éléments :)
La complexité est donc réduite de 2 à 1 itérations, mais toujours la complexité de temps est O (n), vous voulez peut-être mentionner cela dans votre commentaire?
Est-ce bien si je prends votre idée de faire une itération, mais mettez-vous en œuvre d'une autre manière?
@Deveshkumarsingh, ouais, votre réponse LGTM :)
from collections import defaultdict
dic=defaultdict(list)
input_list=[]
for i in range(len(input_list)):
dic[input_list[i]]+=[i]
max_value = max(input_list)
Sol = dic[max_value]
Voici l'approche décrite dans les commentaires. Même si vous utilisez une bibliothèque, fondamentalement, vous devez traverser au moins une fois pour résoudre ce problème (en considérant la liste d'entrée est non formé) . Donc, même la liaison inférieure de l'algorithme serait oméga (taille_of_list). Si la liste est triée, nous pouvons exploiter binary_search pour résoudre le problème.
Cet essai / sauf bloc est totalement inutile. De plus, cette réponse est simplement une version légèrement modifiée d'une ot les autres réponses et ne faisant aucune amélioration.
@Netwave, nous devons peut-être vérifier si c'est une liste vide ou non, c'est simplement un moyen d'effectuer une programmation défensive.
Ce message est juste un échantillon de la façon dont OP veut gérer cette erreur.
Pourquoi ne pas utiliser IndexError à la place? ou vérifier si la liste est vide et élever et exception?
Pensez-y de cette manière, sauf si vous ithérlez via toute la liste une fois, ce qui est Je ne suis donc pas sûr que vous puissiez le faire plus rapidement que O (n) , n étant la longueur de la liste, vous ne pourrez pas comparer le Maximum avec toutes les valeurs de la liste, le meilleur que vous puissiez faire est o (n) , que vous semble déjà faire dans votre exemple.
O (n) avec l'approche de la liste.
Vous faites deux passes, le meilleur que vous puissiez le faire en une seule passe, en gardant une trace du maximum actuel et de tous les index, mais la complexité de la fois de l'algorithme serait toujours
O () ou O (LEN (INPUT_LIST)) .Étant donné que (en CPPHON)
MAX BOUCLES EN C et que votre compréhension de la liste alloue très peu de mémoire supplémentaire, ce que vous avez peut-être déjà optimal (plutôt que simplement asymptotiquement optimal).