Trouver le premier numéro "manquant" dans une liste triée
Disons que j'ai la série continue de nombres entiers [0, 1, 2, 4, 6]
dans lequel le 3
est le premier "manquant" le nombre. J'ai besoin d'un algorithme pour trouver ce premier "trou". Depuis, la gamme est très large (contenant peut-être 2^32
entrées), l'efficacité est importante. La gamme de nombre est stocké sur le disque; l'efficacité de l'espace est également une préoccupation principale.
Quel est le meilleur temps et de l'espace algorithme efficace?
source d'informationauteur zx_wing
Vous devez vous connecter pour publier un commentaire.
Utiliser les binaires de recherche. Si une plage de numéros n'a pas de trou, alors la différence entre la fin et le début de la série sera également le nombre d'entrées dans la gamme.
Vous pouvez donc commencer avec l'ensemble de la liste des numéros, et coupez-soit la première ou de la seconde moitié si le premier semestre a un écart. Finalement, vous arriverez à une plage avec deux entrées avec un trou au milieu.
Le temps de la complexité de ce qui est
O(log N)
. Contrairement à une analyse linéaire, dont le pire des cas estO(N)
.Basée sur l'approche proposée par @phs ci-dessus, voici le code en C pour le faire:
Puisque les chiffres de 0 à n - 1 sont classés dans un tableau, le premier nombre doit être le même que leurs index. C'est-à-dire, le nombre 0 est situé à la cellule avec l'index 0, le nombre 1 est situé dans la cellule avec l'indice 1, et ainsi de suite. Si le nombre manquant est annoncée comme m. Les numéros de moins de m sont situés à des cellules avec des indices de même que sur les valeurs.
Le nombre m + 1 est situé à une cellule avec index mLe nombre m + 2 est situé à une cellule avec index m + 1, et ainsi de suite. Nous pouvons voir que le nombre manquant m est la première cellule dont la valeur n'est pas identique à sa valeur.
Par conséquent, il est nécessaire de rechercher dans un tableau pour trouver la première cellule dont la valeur n'est pas identique à sa valeur. Depuis le tableau est trié, on peut trouver en O(lg n) temps basé sur le binaire de l'algorithme de recherche mis en œuvre ci-dessous:
Cette solution est emprunté à partir de mon blog: http://codercareer.blogspot.com/2013/02/no-37-missing-number-in-array.html.
Basé sur un algorithme fourni par @phs
Avez-vous considéré comme un run-length encoding? Qui est, vous encodez le premier numéro ainsi que le nombre de numéros qui suivent à tour de rôle. Non seulement pouvez-vous vous représenter les nombres utilisés de manière très efficace de cette façon, le premier trou sera à la fin de la première manche-longueur de segment codé.
Pour illustrer votre exemple:
Serait codé comme:
Où x:y les moyens il y a un ensemble de nombres consécutivement en commençant par x pour y des nombres dans une ligne. Cela nous indique immédiatement que le premier trou à l'emplacement 3. Notez, cependant, que ce sera beaucoup plus efficace lorsque les adresses affectées sont regroupés ensemble, et non pas dispersés de manière aléatoire sur toute la gamme.
si la liste est triée, j'avais itérer sur la liste et faire quelque chose comme ce code Python:
si beaucoup de chiffres sont manquant, vous pouvez utiliser @Nathan run-length encoding suggestion pour le
missing
liste.j'en ai eu un algorithme pour trouver le nombre manquant dans la liste triée. sa complexité est logN.
Basé sur un algorithme fourni par @phs
Ci-dessous est ma solution, je crois que c'est simple et évite l'excès de confusion si les relevés. Il fonctionne également lorsque vous ne commencez pas à 0 ou négatif chiffres! La complexité est O(lg n)) temps avec O(1) de l'espace, en supposant que le client est propriétaire le tableau de nombres (sinon c'est O(n)).
L'Algorithme dans le Code C
Sorties De Test
La procédure générale est:
Remarque, l'algorithme hypothèses sont les suivantes:
C'est une Question d'entrevue. Nous avons un tableau de plus d'un manque de chiffres et de nous mettre toutes ces nombres manquants dans une ArrayList.
De la Programmation fonctionnelle de la solution (la Scala)
Évaluation différée
Manquant
Ici
n
est la taille dearray+1
.