Manière efficace de trouver des éléments manquants dans une séquence entière
Supposons que nous avons deux éléments manquants dans une séquence de nombres entiers consécutifs et les éléments manquants se trouvent entre le premier et le dernier éléments. J'ai écrit un code qui fait accomplir la tâche. Cependant, je voulais le rendre efficace en utilisant moins de boucles si possible. Toute aide sera appréciée. Aussi ce sujet de la situation quand nous avons à trouver plus d'éléments manquants (dire proche de n/4) au lieu de 2. Je pense que mon code doit être efficace parce que je suis sortir de la boucle plus tôt?
def missing_elements(L,start,end,missing_num):
complete_list = range(start,end+1)
count = 0
input_index = 0
for item in complete_list:
if item != L[input_index]:
print item
count += 1
else :
input_index += 1
if count > missing_num:
break
def main():
L = [10,11,13,14,15,16,17,18,20]
start = 10
end = 20
missing_elements(L,start,end,2)
if __name__ == "__main__":
main()
source d'informationauteur vkaul11
Vous devez vous connecter pour publier un commentaire.
En supposant que L est une liste d'entiers avec pas de doublons, vous pouvez en déduire que la partie de la liste entre le démarrage et l'indice est complètement consécutives si et seulement si
L[index] == L[start] + (index - start)
et de la même façon avec les index et la fin est complètement consécutives si et seulement siL[index] == L[end] - (end - index)
. Ceci, combiné avec le fractionnement de la liste en deux de manière récursive donne un sublinéaire solution.Si la séquence d'entrée est triésvous pourriez utiliser jeux de ici. Prendre les valeurs début et fin de la liste d'entrée:
Cela suppose Python 3; pour Python 2, utilisez
xrange()
pour éviter la construction d'une liste de la première.La
sorted()
appel est facultatif; sans elle, unset()
est retourné des valeurs manquantes, avec elle, vous obtenez une liste triée.Démo:
Une autre approche consiste à détecter les écarts entre les nombres ultérieur; l'aide d'une ancienne
itertools
de la bibliothèque de la fenêtre de glissement de la recette:C'est un pur O(n), et si vous connaissez le nombre d'articles manquants, vous pouvez vous assurer qu'il ne produit de ceux-ci et puis s'arrête:
Cela permettra de traiter de plus grandes lacunes trop; si vous êtes en manque 2 articles 11 et 12, ça va encore travailler:
et l'exemple ci-dessus n'avait qu'à itérer sur
[10, 13]
.À l'aide de
scipy
lib:Calendrier:
Autre option est:
Et le timing est:
De mon point de vue a été de ne pas utiliser les boucles et les opérations sur les ensembles:
Simplement marcher sur la liste pour rechercher numéros non consécutifs:
Voici un one-liner:
- Je utiliser la liste, de tranchage pour compenser les copies par l'un, et l'utilisation d'énumérer pour obtenir les indices de l'article manquant.
Pour de longues listes, ce n'est pas grand, car il n'est pas O(log(n)), mais je pense qu'il devrait être assez efficace, plutôt que d'utiliser une
set
pour les petites entrées.izip
de itertools serait probablement rendre plus rapide encore.À l'aide de
collections.Compteur
:De sortie:
Nous avons trouvé une valeur manquante si la différence entre deux nombres consécutifs est supérieur à
1
:Note: Python 3. En Python 2 utilisez
itertools.izip
.Version améliorée pour plus d'une valeur manquante dans une rangée:
Il convient tout d'abord de trier la liste et ensuite on vérifie pour chaque élément, à l'exception de la dernière, si la nouvelle valeur dans la liste. Veillez à ne pas avoir des doublons dans la liste!