Gegeben ein Array von N ganzen Zahlen, so dass nur eine ganze Zahl wiederholt wird. Finde die wiederholte Ganzzahl in O (n) Zeit und konstantem Raum. Es gibt keinen Bereich für den Wert von Ganzzahlen oder den Wert von N
Zum Beispiel ein Array von 6 ganzen Zahlen wie 23 45 67 87 23 47. Die Antwort ist 23 (Ich hoffe, dies deckt mehrdeutige und vage Teil)
Ich habe im Internet gesucht, konnte aber keine solche Frage finden, bei der der Bereich der ganzen Zahlen nicht festgelegt war. Auch hier ist ein Beispiel, das mir eine ähnliche Frage beantwortet, aber hier hat er einen Hash erstellt Tabelle mit dem höchsten Integer-Wert in C ++, aber die cpp erlaubt es nicht, so ein Array mit 2 ^ 64 Element (auf einem 64-Bit-Computer) zu erstellen.
Es tut mir leid, dass ich es nicht erwähnt habe, bevor das Array unveränderlich ist
Jun Tarui hat gezeigt , dass alle doppelten Sucher, die O (log n) Platz benötigt mindestens Ω (log n / log log n), was die lineare Zeit überschreitet. I.e. Ihre Frage ist nachweisbar unlösbar, selbst wenn Sie den logarithmischen Raum zulassen.
Es gibt einen interessanten Algorithmus von Gopalan und Radhakrishnan, der Duplikate in einem Durchgang über die Eingabe findet O ((log n) ^ 3) Raum, der a priori nach der besten Wette klingt.
Radix sort hat eine Zeitkomplexität O (kn) wo k & gt; log_2 n wird oft als Konstante betrachtet, wenn auch als große Konstante. Sie können eine Radix-Sortierung natürlich nicht im konstanten Bereich implementieren, aber Sie könnten den Speicherplatz Ihrer Eingabedaten möglicherweise wiederverwenden.
Es gibt numerische Tricks, wenn Sie Merkmale über die Zahlen selbst annehmen. Wenn fast alle Zahlen zwischen 1 und n vorhanden sind, addiere sie einfach und subtrahiere n (n + 1) / 2. Wenn alle Zahlen Primzahlen sind, könnten Sie schummeln, indem Sie die Laufzeit der Division ignorieren.
Nebenbei bemerkt, gibt es eine bekannte Untergrenze von Ω (log_2 (n!)) bei der Vergleichssortierung, was darauf hindeutet, dass Google Ihnen helfen könnte, bei einfachen Problemen, wie dem Auffinden von Duplikaten, niedrigere Grenzen zu finden.
>Wenn der Bereich der Ganzzahlen begrenzt ist, können Sie eine Variante zum Zählen sortieren in O ( n) ausführen ) Zeit. Die Raumkomplexität ist O ( k ), wobei k die obere Grenze für die Ganzzahlen (*) ist, aber das ist eine Konstante, also ist es O (1).
Wenn der Bereich der Ganzzahlen unbegrenzt ist, dann glaube ich nicht, dass es irgendeinen Weg dafür gibt, aber ich bin kein Experte für Komplexitätsrätsel.
(*) Es ist O (k), da es auch eine konstante obere Schranke für die Anzahl der Vorkommen jeder Ganzzahl gibt, nämlich 2.
Wenn die Einträge durch die Länge des Arrays begrenzt sind, können Sie Suchen Sie eine beliebige von mehreren möglichen wiederholten Ganzzahlen in einer Liste und die O (N) Zeit und O (1) Raum Lösung .
Die von Ihnen erwähnte Verallgemeinerung wird in dieser Nachfolgefrage erläutert: Algorithmus, um eine wiederholte Nummer in einer Liste zu finden, die eine beliebige Anzahl von Wiederholungen enthalten kann und die O (n log ^ 2 n) Zeit und O (1) Raumlösung .
Der Ansatz, der O (N) zeitlich am nächsten kommt, ist wahrscheinlich eine konventionelle Hash-Tabelle, bei der die Hash-Einträge einfach die Zahlen sind, die als Schlüssel verwendet werden. Sie würden durch die Liste gehen und jeden Eintrag in die Hash-Tabelle einfügen, nachdem Sie zuerst überprüft haben, ob sie bereits in der Tabelle enthalten ist.
Nicht streng O (N), da die Hash-Suche / -Einfügung langsamer wird, wenn die Tabelle voll ist. Und in Bezug auf die Speicherung wäre es teuer für große Listen - mindestens 3x und möglicherweise 10-20x die Größe des Arrays von Zahlen.
Wie schon von anderen erwähnt, sehe ich keinen Weg, es in O (n) zu machen.
Sie können jedoch einen probabilistischen Ansatz versuchen, indem Sie einen Bloom-Filter verwenden. Es wird dir O (n) geben, wenn du Glück hast.
Da zusätzlicher Platz nicht erlaubt ist, kann dies nicht ohne Vergleich getan werden. Das Konzept der unteren Grenze für die Zeitkomplexität von Vergleichssorte kann hier angewendet werden, um zu beweisen, dass das Problem in seiner ursprünglichen Form im schlimmsten Fall nicht in O (n) gelöst werden kann.