Trouver un «trou» dans une liste de nombres

14

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?

Fabian Zeindl
la source
6
@Jodrell Je pense que trier une progression infinie serait difficile ;-)
maple_shaft
3
@maple_shaft a accepté, cela pourrait prendre un certain temps.
Jodrell
4
Comment définissez-vous d'abord une liste non triée?
Jodrell
1
Je viens de réaliser que cela appartient probablement à StackOverflow, car ce n'est pas vraiment un problème conceptuel.
JasonTrue
2
@JasonTrue De la FAQ, If you have a question about… •algorithm and data structure conceptsc'est sur le sujet à mon humble avis .
maple_shaft

Réponses:

29

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.

JasonTrue
la source
6
Eh bien, à titre de comparaison directe, si vous aviez tous des entiers 32 bits non signés positifs mais 1, vous pourriez résoudre le problème d'entier manquant dans environ un demi-gigaoctet de mémoire. Si vous triiez à la place, vous devrez utiliser plus de 8 gigaoctets de mémoire. Et le tri, sauf dans des cas spéciaux comme celui-ci (votre liste est triée une fois que vous avez un vecteur de bits) est presque toujours n log n ou pire, donc sauf dans les cas où la constante l'emporte sur la complexité des coûts, l'approche linéaire l'emporte.
JasonTrue
1
Et si vous ne connaissez pas la gamme a priori?
Blrfl
2
Si vous avez un type de données entier, Blrfl, vous connaissez certainement l'étendue maximale de la plage, même si vous ne disposez pas de suffisamment d'informations pour affiner davantage. Si vous savez qu'il s'agit d'une petite liste, mais que vous ne connaissez pas la taille exacte, le tri peut être une solution plus simple.
JasonTrue
1
Ou faites d'abord une autre boucle dans la liste pour trouver le plus petit et le plus grand élément. Ensuite, vous pouvez allouer un tableau de taille exacte avec la plus petite valeur comme décalage de base. Toujours sur).
Sécurisé le
1
@JPatrick: Pas les devoirs, les affaires, j'ai obtenu mon diplôme il y a des années :).
Fabian Zeindl
4

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 .

Jim G.
la source
Une question, comment identifiez-vous les "plus petits" éléments de la liste?
Jodrell
4

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).

KeithS
la source
C'est ridiculement intelligent et génial! Maintenant, pouvez-vous trouver un moyen de le faire avec un nombre variable de trous? :-D
2

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.

Peter Smith
la source
1

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 .

pillmuncher
la source
1
Voulez-vous dire que parcourir une liste est la même complexité temporelle que le tri?
maple_shaft
@maple_shaft: Non, je dis que construire un arbre binaire à partir de données aléatoires puis le parcourir de gauche à droite équivaut à trier puis à passer de petit à grand.
pillmuncher
1

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.

Gerenuk
la source
0

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 .

aufather
la source
0

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.

Kevin
la source
1
Je ne crois pas que le PO ait dit qu'il n'y avait qu'un seul trou. L'entrée est une liste non triée de nombres - ils peuvent être n'importe quoi. D'après votre description, la façon dont vous déterminez le nombre de "nombres" ne devrait pas être claire.
Caleb
@caleb Peu importe le nombre de trous, juste pas de doublons (qui peuvent être supprimés dans O (N) avec un ensemble de hachage, bien qu'en pratique cela puisse avoir plus de surcharge que les autres méthodes). J'ai essayé d'améliorer la description, voyez si c'est mieux.
Kevin
Ce n'est pas linéaire, OMI. C'est plus comme (logN) ^ 2. À chaque étape, vous faites pivoter le sous-ensemble de la collection qui vous intéresse (la moitié du sous-tableau précédent que vous avez identifié comme ayant le premier "trou"), puis récursivement dans le côté gauche s'il a un "trou", ou le côté droit si le côté gauche ne fonctionne pas. (logN) ^ 2 est toujours meilleur que linéaire; si N décuple, vous ne faites que de l'ordre de 2 (log (N) -1) + 1 pas de plus.
KeithS
@Keith - malheureusement, vous devez regarder tous les nombres à chaque niveau pour les faire pivoter, il faudra donc environ n + n / 2 + n / 4 + ... = 2n (techniquement, 2 (nm)) comparaisons .
Kevin