J'ai une liste dans laquelle les éléments sont déjà triés. Je veux filtrer des éléments supérieurs à un nombre donné.
Par exemple, P>
original_list = [2,3,5,7,11] limit = 6 expected_list = [2,3,5] # All elements <=6
4 Réponses :
import bisect original_list = [2,3,5,7,11] limit = 6 expected_list = [2,3,5] # All elements <=6 index = bisect.bisect(original_list, limit) filtered = original_list[:index] assert filtered == expected_list
Voici 2 approches:
[2, 3, 5] [2, 3, 5]
comment venir? Lorsque vous calculez BIG O, vous prenez en compte le pire des cas
Eh bien, si vous voulez à ce niveau de détails, mais vous ne le faites pas, mais pour le pendant que boucle est O (n) depuis le pire des scénarios sera si limite = n
L'algorithme de bidissure est une recherche binaire de sorte qu'elle est O (logn), vous pouvez avoir un look ici Stackoverflow.com/questions/12022249/...
Je suis d'accord sur cela, mais qu'il n'incluait pas dans le pendant la solution de boucle
Si votre liste est triée par ordre croissant et que vous souhaitez une valeur sous certains seuils, vous pouvez utiliser ITERTOOLS.TAKEWHIE SUIVANT:
import itertools original_list = [2,3,5,7,11] limit = 6 expected_list = list(itertools.takewhile(lambda x:x<=limit, original_list)) print(expected_list) # [2, 3, 5]
Pouvons-nous utiliser la compréhension de la liste ici,
expected_list = [value for value in original_list if value < limit]
L'OP a demandé le moyen le plus efficace des tableaux triés. Comme vous la solution, une solution sera itinératrice sur toutes les valeurs de la liste, cette solution n'est pas la voie à suivre ici.
5 est sur l'élément moyen, vous pouvez définir l'élément moyen
mid = len (original_list) \\ 2 et ensuite définir comme x = original_list [: moyen]@ M3duza mais si ce n'est pas? Et si le
limite est8 ?@ M3duza La liste est déjà triée, vous n'avez pas besoin de traverser à chaque fois que le dernier élément.