Trouver un «trou» dans une liste de nombres

Quel est le moyen le plus rapide de trouver le premier (plus petit) entier qui n'existe pas dans une liste donnée d' entiers non triés (et qui est supérieur à la plus petite valeur de la liste)?

Mon approche primitive consiste à les trier et à parcourir la liste, y a-t-il une meilleure façon?

En supposant que vous voulez dire "entier" lorsque vous dites "nombre", vous pouvez utiliser un vecteur de bits de taille 2 ^ n, où n est le nombre d'éléments (par exemple, votre plage comprend des entiers compris entre 1 et 256, alors vous pouvez utiliser un 256- bit ou 32 octets, bitvector). Lorsque vous rencontrez un entier en position n de votre plage, définissez le nième bit.

Lorsque vous avez fini d'énumérer la collection d'entiers, vous parcourez les bits de votre vecteur de bits, en recherchant la position de tout ensemble de bits 0. Ils correspondent maintenant à la position n de votre ou vos nombres entiers manquants.

C'est O (2 * N), donc O (N) et probablement plus efficace en mémoire que le tri de la liste entière.

Si vous triez d'abord la liste entière, vous garantissez l'exécution dans le pire des cas. En outre, votre choix d'algorithme de tri est essentiel.

Voici comment j'aborderais ce problème:

1. Utilisez une sorte de tas , en se concentrant sur les plus petits éléments de la liste.
2. Après chaque échange, voyez si vous avez un écart.
3. Si vous trouvez une lacune, alors return: Vous avez trouvé votre réponse.
4. Si vous ne trouvez pas d'écart, continuez à échanger.

Voici une visualisation d'une sorte de tas .

Juste pour être ésotérique et "intelligent", dans le cas particulier de la baie n'ayant qu'un "trou", vous pouvez essayer une solution basée sur XOR:

• Déterminez la plage de votre baie; cela se fait en définissant une variable "max" et "min" sur le premier élément du tableau, et pour chaque élément après cela, si cet élément est inférieur au min ou supérieur au max, définissez le min ou max sur le nouvelle valeur.
• Si la plage est inférieure de un à la cardinalité de l'ensemble, il n'y a qu'un seul "trou" pour que vous puissiez utiliser XOR.
• Initialisez une variable entière X à zéro.
• Pour chaque entier de min à max inclusivement, XOR cette valeur avec X et stocker le résultat dans X.
• Maintenant, XOR chaque entier du tableau avec X, stockant chaque résultat successif dans X comme précédemment.
• Lorsque vous avez terminé, X sera la valeur de votre "trou".

Cela fonctionnera dans environ 2N temps, similaire à la solution bitvector, mais nécessite moins d'espace mémoire pour tout N> sizeof (int). Cependant, si le réseau a plusieurs "trous", X sera la "somme" XOR de tous les trous, ce qui sera difficile, voire impossible, à séparer en valeurs réelles des trous. Dans ce cas, vous revenez à une autre méthode telle que les approches "pivot" ou "bitvector" d'autres réponses.

Vous pouvez également récapituler cela en utilisant quelque chose de similaire à la méthode pivot pour réduire davantage la complexité. Réorganisez le tableau en fonction d'un point de pivot (qui sera le max du côté gauche et le min de la droite; il sera trivial de trouver le max et le min du tableau complet lors du pivotement). Si le côté gauche du pivot comporte un ou plusieurs trous, rentrez uniquement dans ce côté; sinon rentrez de l'autre côté. À tout moment où vous pouvez déterminer qu'il n'y a qu'un seul trou, utilisez la méthode XOR pour le trouver (ce qui devrait être moins cher dans l'ensemble que de continuer à pivoter jusqu'à une collection de deux éléments avec un trou connu, qui est le cas de base pour l'algorithme de pivot pur).

Quelle est la gamme de nombres que vous rencontrerez? Si cette plage n'est pas très grande, vous pouvez résoudre ce problème avec deux scans (temps linéaire O (n)) en utilisant un tableau avec autant d'éléments que vous avez de nombres, en échangeant de l'espace contre du temps. Vous pouvez trouver la plage dynamiquement avec un scan de plus. Pour réduire l'espace, vous pouvez attribuer 1 bit à chaque numéro, ce qui vous donne 8 numéros de stockage par octet.

Votre autre option, qui peut être meilleure pour les premiers scénarios et qui serait insituée au lieu de copier la mémoire, est de modifier le tri de sélection pour quitter tôt si le min trouvé dans un passage de numérisation n'est pas supérieur de 1 à la dernière min trouvée.

Non, pas vraiment. Étant donné que tout numéro non encore scanné peut toujours être celui qui remplit un "trou" donné, vous ne pouvez pas éviter de scanner chaque numéro au moins une fois, puis de le comparer à ses voisins possibles. Vous pourriez probablement accélérer les choses en construisant un arbre binaire, puis en le parcourant de gauche à droite jusqu'à ce qu'un trou soit trouvé, mais c'est essentiellement de la même complexité que le tri, car il s'agit d'un tri. Et vous ne trouverez probablement rien de plus rapide que Timsort .

La plupart des idées ici ne sont rien d'autre que du tri. La version bitvector est un simple Bucketsort. Le tri en tas a également été mentionné. Cela revient essentiellement à choisir le bon algorithme de tri qui dépend des exigences de temps / d'espace ainsi que de la plage et du nombre d'éléments.

À mon avis, l'utilisation d'une structure de tas est probablement la solution la plus générale (un tas vous donne essentiellement les plus petits éléments efficacement sans tri complet).

Vous pouvez également analyser les approches qui trouvent d'abord les plus petits nombres, puis rechercher chaque entier supérieur à celui-ci. Ou vous trouvez les 5 plus petits nombres en espérant qu'il y aura un écart.

Tous ces algorithmes ont leur force en fonction des caractéristiques d'entrée et des exigences du programme.

Une solution qui n'utilise pas de stockage supplémentaire ou n'assume pas la largeur (32 bits) des entiers.

1. Dans un passage linéaire, trouvez le plus petit nombre. Appelons cela "min". O (n) complexité temporelle.

2. Choisissez un élément pivot aléatoire et faites une partition de style quicksort.

3. Si le pivot s'est retrouvé dans la position = ("pivot" - "min"), alors récursif sur le côté droit de la partition, sinon récursif sur le côté gauche de la partition. L'idée ici est que s'il n'y a pas de trous depuis le début, le pivot serait en position ("pivot" - "min"), donc le premier trou devrait se trouver à droite de la partition et vice versa.

4. Le cas de base est un tableau de 1 élément et le trou se situe entre cet élément et le suivant.

La complexité totale attendue du temps de fonctionnement est O (n) (8 * n avec les constantes) et le pire des cas est O (n ^ 2). L'analyse de la complexité temporelle d'un problème similaire peut être trouvée ici .

Je crois que j'ai trouvé quelque chose qui devrait fonctionner de manière générale et efficace si vous êtes assuré de ne pas avoir de doublons * (cependant, il devrait être extensible à n'importe quel nombre de trous et à toute plage d'entiers).

L'idée derrière cette méthode est comme le tri rapide, en ce sens que nous trouvons un pivot et une partition autour d'elle, puis récurons sur le ou les côtés avec un trou. Pour voir quels côtés ont le trou, nous trouvons les nombres les plus bas et les plus élevés, et les comparons avec le pivot et le nombre de valeurs de ce côté. Disons que le pivot est 17 et que le nombre minimum est 11. S'il n'y a pas de trous, il devrait y avoir 6 nombres (11, 12, 13, 14, 15, 16, 17). S'il y en a 5, nous savons qu'il y a un trou de ce côté et nous pouvons recurse juste de ce côté pour le trouver. J'ai du mal à l'expliquer plus clairement que cela, alors prenons un exemple.

15 21 10 13 18 16 22 23 24 20 17 11 25 12 14

Pivot:

10 13 11 12 14 |15| 21 18 16 22 23 24 20 17 25

15 est le pivot, indiqué par les tuyaux ( ||). Il y a 5 chiffres sur le côté gauche du pivot, comme il devrait y en avoir (15 - 10), et 9 sur la droite, où il devrait y en avoir 10 (25 - 15). Nous récurons donc du côté droit; on notera que la borne précédente était de 15 au cas où le trou lui serait adjacent (16).

[15] 18 16 17 20 |21| 22 23 24 25

Il y a maintenant 4 chiffres sur le côté gauche mais il devrait y en avoir 5 (21 - 16). Donc, nous recursons là-bas, et encore une fois, nous noterons la borne précédente (entre parenthèses).

[15] 16 17 |18| 20 [21]

Le côté gauche a les 2 bons chiffres (18 - 16), mais le droit a 1 au lieu de 2 (20 - 18). En fonction de nos conditions de fin, nous pourrions comparer le nombre 1 aux deux côtés (18, 20) et voir que 19 est manquant ou récidiver une fois de plus:

[18] |20| [21]

Le côté gauche a une taille de zéro, avec un espace entre le pivot (20) et la limite précédente (18), donc 19 est le trou.

*: S'il y a des doublons, vous pourriez probablement utiliser un ensemble de hachage pour les supprimer en temps O (N), en conservant la méthode globale O (N), mais cela pourrait prendre plus de temps que d'utiliser une autre méthode.