Finden Sie ein "Loch" in einer Liste von Zahlen

14

Was ist der schnellste Weg, um die erste (kleinste) Ganzzahl zu finden, die in einer gegebenen Liste unsortierter Ganzzahlen nicht existiert (und die größer ist als der kleinste Wert der Liste)?

Mein primitiver Ansatz besteht darin, sie zu sortieren und die Liste durchzugehen. Gibt es einen besseren Weg?

Fabian Zeindl
quelle
6
@ Jodrell Ich denke, es wäre schwierig, eine unendliche Entwicklung zu sortieren
;-)
3
@maple_shaft stimmte zu, könnte eine Weile dauern.
Jodrell
4
Wie definieren Sie zuerst eine unsortierte Liste?
Jodrell,
1
Ich habe gerade festgestellt, dass dies wahrscheinlich zu StackOverflow gehört, da es sich nicht wirklich um ein konzeptionelles Problem handelt.
JasonTrue
2
@ JasonTrue Aus der FAQ, If you have a question about… •algorithm and data structure conceptses ist zum Thema IMHO.
maple_shaft

Antworten:

29

Angenommen, Sie meinen "Ganzzahl", wenn Sie "Zahl" sagen, können Sie einen Bitvektor der Größe 2 ^ n verwenden, wobei n die Anzahl der Elemente ist (sagen, Ihr Bereich umfasst Ganzzahlen zwischen 1 und 256, dann können Sie einen 256- bit oder 32 byte bitvector). Wenn Sie auf eine Ganzzahl in Position n Ihres Bereichs stoßen, setzen Sie das n-te Bit.

Wenn Sie die Auflistung der Ganzzahlen abgeschlossen haben, iterieren Sie über die Bits in Ihrem Bitvektor und suchen nach der Position aller Bits, die auf 0 gesetzt sind. Sie stimmen nun mit der Position n der fehlenden Ganzzahlen überein.

Dies ist O (2 * N), daher O (N) und wahrscheinlich speichereffizienter als das Sortieren der gesamten Liste.

JasonTrue
quelle
6
Nun, als direkter Vergleich, wenn Sie alle positiven vorzeichenlosen 32-Bit-Ganzzahlen außer 1 hätten, könnten Sie das Problem der fehlenden Ganzzahlen in etwa einem halben Gigabyte Speicher lösen. Wenn Sie stattdessen sortieren, müssen Sie über 8 Gigabyte Arbeitsspeicher verwenden. Und das Sortieren, außer in speziellen Fällen wie diesem (Ihre Liste wird sortiert, sobald Sie einen Bitvektor haben), ist fast immer n log n oder schlechter. Wenn also die Konstante die Komplexität der Kosten überwiegt, gewinnt der lineare Ansatz.
JasonTrue
1
Was ist, wenn Sie die Reichweite a priori nicht kennen?
Blrfl
2
Wenn Sie einen ganzzahligen Datentyp, Blrfl, haben, kennen Sie sicherlich die maximalen Ausmaße des Bereichs, auch wenn Sie nicht genügend Informationen haben, um weiter einzugrenzen. Wenn Sie zufällig wissen, dass es sich um eine kleine Liste handelt, die genaue Größe jedoch nicht bekannt ist, ist das Sortieren möglicherweise eine einfachere Lösung.
JasonTrue
1
Oder durchlaufen Sie die Liste erneut, um das kleinste und das größte Element zu finden. Dann können Sie ein Array mit exakter Größe mit dem kleinsten Wert als Basisoffset zuweisen. Immernoch an).
Sichern Sie sich den
1
@JPatrick: Keine Hausaufgaben, Geschäft, ich habe CS vor Jahren absolviert :).
Fabian Zeindl
4

Wenn Sie zuerst die gesamte Liste sortieren, ist die Laufzeit im ungünstigsten Fall garantiert. Auch Ihre Wahl des Sortieralgorithmus ist entscheidend.

So würde ich dieses Problem angehen:

  1. Verwenden Sie eine Heap-Sortierung , die sich auf die kleinsten Elemente in der Liste konzentriert.
  2. Prüfen Sie nach jedem Tausch, ob Sie eine Lücke haben.
  3. Wenn Sie eine Lücke finden, dann return: Sie haben Ihre Antwort gefunden.
  4. Wenn Sie keine Lücke finden, tauschen Sie weiter.

Hier ist eine Visualisierung einer Heap-Sortierung .

Jim G.
quelle
Eine Frage, wie identifizieren Sie die "kleinsten" Elemente der Liste?
Jodrell
4

Um esoterisch und "clever" zu sein, können Sie im speziellen Fall eines Arrays mit nur einem "Loch" eine XOR-basierte Lösung ausprobieren:

  • Bestimmen Sie die Reichweite Ihres Arrays. Dies erfolgt durch Setzen einer "max" - und "min" -Variable auf das erste Element des Arrays. Wenn dieses Element danach für jedes Element kleiner als das min oder größer als das max ist, setzen Sie das min oder max auf das neuer Wert.
  • Wenn der Bereich um eins kleiner als die Kardinalität des Satzes ist, gibt es nur ein "Loch", sodass Sie XOR verwenden können.
  • Initialisieren Sie eine Ganzzahlvariable X auf Null.
  • XOREN Sie für jede ganze Zahl von min bis max diesen Wert mit X und speichern Sie das Ergebnis in X.
  • Nun XOR jede ganze Zahl im Array mit X, wobei jedes nachfolgende Ergebnis wie zuvor in X gespeichert wird.
  • Wenn Sie fertig sind, wird X der Wert Ihres "Lochs" sein.

Dies dauert ungefähr 2N, ähnlich wie bei der Bitvector-Lösung, erfordert jedoch weniger Speicherplatz für N> sizeof (int). Wenn das Array jedoch mehrere "Löcher" hat, ist X die XOR "Summe" aller Löcher, die sich nur schwer oder gar nicht in die tatsächlichen Lochwerte aufteilen lassen. In diesem Fall greifen Sie auf eine andere Methode zurück, z. B. die Ansätze "Pivot" oder "Bitvector" aus anderen Antworten.

Sie können dies auch mithilfe der Pivot-Methode wiederholen, um die Komplexität weiter zu verringern. Ordnen Sie das Array basierend auf einem Drehpunkt neu an (der das Maximum der linken und das Minimum der rechten Seite ist; es ist trivial, das Maximum und das Minimum des vollständigen Arrays beim Drehen zu ermitteln). Wenn die linke Seite des Zapfens ein oder mehrere Löcher hat, greifen Sie nur auf diese Seite zurück. ansonsten auf die andere Seite zurückgreifen. Verwenden Sie an jedem Punkt, an dem Sie feststellen können, dass es nur ein Loch gibt, die XOR-Methode, um es zu finden (die insgesamt günstiger sein sollte, als wenn Sie weiter bis zu einer Ansammlung von zwei Elementen mit einem bekannten Loch schwenken, für das der Basisfall gilt) der reine Pivot-Algorithmus).

KeithS
quelle
Das ist lächerlich schlau und genial! Können Sie jetzt einen Weg finden, dies mit einer variablen Anzahl von Löchern zu tun? :-D
2

Welchem ​​Zahlenbereich werden Sie begegnen? Wenn dieser Bereich nicht sehr groß ist, können Sie dies mit zwei Scans (lineare Zeit O (n)) lösen, indem Sie ein Array mit so vielen Elementen verwenden, wie Sie Zahlen haben, und dabei Raum gegen Zeit tauschen. Sie können den Bereich mit einem weiteren Scan dynamisch ermitteln. Um den Speicherplatz zu verringern, können Sie jeder Zahl 1 Bit zuweisen, wodurch Sie 8 Speicherplätze pro Byte erhalten.

Die andere Option, die für frühe Szenarien besser geeignet ist und sich statt des Kopierens des Speichers in situ befindet, besteht darin, die Auswahlsortierung so zu ändern, dass sie vorzeitig beendet wird, wenn die in einem Scan-Durchgang gefundene Minute nicht um 1 höher ist als die zuletzt gefundene Minute.

Peter Smith
quelle
1

Nein nicht wirklich. Da jede noch nicht gescannte Nummer immer eine sein kann, die ein bestimmtes "Loch" ausfüllt, können Sie nicht vermeiden, jede Nummer mindestens einmal zu scannen und sie dann mit ihren möglichen Nachbarn zu vergleichen. Sie könnten die Dinge wahrscheinlich beschleunigen, indem Sie einen binären Baum aufbauen und ihn dann von links nach rechts durchlaufen, bis ein Loch gefunden wird. Dies ist jedoch im Wesentlichen genauso komplex wie das Sortieren, da es sich um das Sortieren handelt. Und Sie werden wahrscheinlich nichts schnelleres als Timsort finden .

Pillmuncher
quelle
1
Wollen Sie damit sagen, dass das Durchlaufen einer Liste genauso viel Zeit kostet wie das Sortieren?
maple_shaft
@maple_shaft: Nein, ich sage, das Erstellen eines Binärbaums aus zufälligen Daten und das anschließende Überqueren von links nach rechts entspricht dem Sortieren und anschließenden Überqueren von klein nach groß.
Pillmuncher
1

Die meisten Ideen hier sind nicht mehr als nur Sortieren. Die Bitvector-Version ist schlicht Bucketsort. Haufenart wurde auch erwähnt. Es läuft im Wesentlichen darauf hinaus, den richtigen Sortieralgorithmus auszuwählen, der von den zeitlichen und räumlichen Anforderungen sowie vom Umfang und der Anzahl der Elemente abhängt.

Aus meiner Sicht ist die Verwendung einer Heap-Struktur wahrscheinlich die allgemeinste Lösung (ein Heap liefert im Grunde genommen die kleinsten Elemente ohne vollständige Sortierung).

Sie können auch Ansätze analysieren, die zuerst die kleinsten Zahlen finden und dann nach jeder größeren Ganzzahl suchen. Oder Sie finden die 5 kleinsten Zahlen in der Hoffnung, dass sie eine Lücke haben.

Alle diese Algorithmen haben ihre Stärke in Abhängigkeit von den Eingabeeigenschaften und den Programmanforderungen.

Gerenuk
quelle
0

Eine Lösung, die keinen zusätzlichen Speicher verwendet oder die Breite (32 Bit) von Ganzzahlen annimmt.

  1. Finden Sie in einem Durchgang die kleinste Zahl. Nennen wir dies "min". O (n) zeitliche Komplexität.

  2. Wählen Sie ein zufälliges Pivot-Element und erstellen Sie eine Partition im QuickSort-Stil.

  3. Wenn der Pivot in der Position = ("Pivot" - "min") endete, dann rekursiv auf der rechten Seite der Partition, andernfalls rekursiv auf der linken Seite der Partition. Die Idee dabei ist, dass, wenn von Anfang an keine Löcher vorhanden sind, sich der Drehpunkt in der Position ("Drehpunkt" - "min") befinden würde, sodass das erste Loch rechts von der Trennwand liegen sollte und umgekehrt.

  4. Basisfall ist ein Array von 1 Element und die Bohrung liegt zwischen diesem und dem nächsten Element.

Die erwartete Gesamtlaufzeitkomplexität ist O (n) (8 * n mit den Konstanten) und der schlechteste Fall ist O (n ^ 2). Die Zeitkomplexitätsanalyse für ein ähnliches Problem finden Sie hier .

aufather
quelle
0

Ich glaube, ich habe etwas gefunden, das allgemein und effizient funktionieren sollte, wenn Sie garantiert keine Duplikate haben * (es sollte jedoch auf eine beliebige Anzahl von Löchern und einen beliebigen Bereich von ganzen Zahlen erweiterbar sein).

Die Idee hinter dieser Methode ist wie bei der Quicksort-Methode, bei der wir einen Drehpunkt und eine Trennwand finden und dann auf die Seite (n) mit einem Loch zurückgreifen. Um zu sehen, welche Seiten das Loch haben, ermitteln wir die niedrigsten und höchsten Zahlen und vergleichen sie mit dem Drehpunkt und der Anzahl der Werte auf dieser Seite. Angenommen, der Drehpunkt ist 17 und die Mindestanzahl ist 11. Wenn keine Löcher vorhanden sind, sollten 6 Zahlen vorhanden sein (11, 12, 13, 14, 15, 16, 17). Wenn es 5 gibt, wissen wir, dass es auf dieser Seite ein Loch gibt, und wir können nur auf dieser Seite zurückgreifen, um es zu finden. Ich habe Probleme, es klarer zu erklären. Nehmen wir also ein Beispiel.

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

Drehpunkt:

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

15 ist der Drehpunkt, angezeigt durch Rohre ( ||). Es gibt 5 Zahlen auf der linken Seite des Pivots, wie es sein sollte (15 - 10), und 9 auf der rechten Seite, wo es 10 sein sollte (25 - 15). Wir kehren also auf die rechte Seite zurück. Wir werden bemerken, dass die vorherige Grenze 15 war, falls das Loch daneben liegt (16).

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

Jetzt gibt es 4 Zahlen auf der linken Seite, aber es sollten 5 sein (21 - 16). Wir kehren dort also zurück und notieren erneut die vorherige Schranke (in Klammern).

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

Die linke Seite hat die richtigen 2 Zahlen (18 - 16), aber die rechte hat 1 anstelle von 2 (20 - 18). Abhängig von unseren Endebedingungen können wir die 1-Zahl mit den beiden Seiten (18, 20) vergleichen und feststellen, dass 19 fehlt oder noch einmal verwendet wird:

[18] |20| [21]

Die linke Seite hat eine Größe von Null, mit einer Lücke zwischen dem Zapfen (20) und der vorherigen Grenze (18), also ist 19 das Loch.

*: Wenn Duplikate vorhanden sind, können Sie diese möglicherweise mithilfe eines Hash-Satzes in O (N) entfernen, wobei die Gesamtmethode O (N) beibehalten wird. Dies kann jedoch mehr Zeit in Anspruch nehmen als die Verwendung einer anderen Methode.

Kevin
quelle
1
Ich glaube nicht, dass das OP irgendetwas darüber gesagt hat, dass es nur ein Loch gibt. Die Eingabe ist eine unsortierte Liste von Zahlen - es kann sich um alles handeln. Aus Ihrer Beschreibung ist nicht ersichtlich, wie viele Zahlen dort "sein sollten".
Caleb
@caleb Es spielt keine Rolle, wie viele Löcher es gibt, nur keine Duplikate (die in O (N) mit einem Hash-Set entfernt werden können, obwohl dies in der Praxis möglicherweise mehr Overhead bedeutet als andere Methoden). Ich habe versucht, die Beschreibung zu verbessern und zu prüfen, ob sie besser ist.
Kevin
Das ist nicht linear, IMO. Es ist eher wie (logN) ^ 2. Bei jedem Schritt schwenken Sie die Teilmenge der Sammlung, die Sie interessiert (die Hälfte des vorherigen Teilarrays, das Sie als das erste "Loch" identifiziert haben), und kehren dann in eine der beiden linken Seiten zurück, wenn es ein "Loch" hat. oder die rechte Seite, wenn die linke Seite nicht. (logN) ^ 2 ist immer noch besser als linear; Wenn sich N verzehnfacht, nehmen Sie nur die Größenordnung von 2 (log (N) -1) + 1 weitere Schritte an.
KeithS
@Keith - leider muss man sich alle Zahlen auf jeder Ebene ansehen, um sie zu pivotisieren. Es dauert also ungefähr n + n / 2 + n / 4 + ... = 2n (technisch gesehen 2 (nm)) Vergleiche .
Kevin