Pflegen Sie einen sortierten array in O(1)?
Wir haben ein sortiertes array, und wir möchten, erhöhen Sie den Wert von einem index von nur 1 Einheit (array[i]++), so dass das resultierende array wird noch sortiert. Ist das möglich in O(1)?
Es ist in Ordnung für beliebige Daten verwenden, die Struktur möglich in STL und C++.
In einen spezielleren Fall, wenn das array wird initialisiert, indem alle 0-Werte, und es ist immer inkrementell konstruiert, die nur durch erhöhen den Wert eines index ist, ist es eine O(1) Lösung???
- Sicher, es kann. Ich glaube, wenn es keine wiederholten Elemente, dann würden wir nur müssen Sie eine swap-und es ist sortiert.
- Recht. Ich erkannte, dass, sobald ich Lesen Sie den Teil, wo Sie sagte, das array wird mit 0 initialisiert ist. 🙂
- Ist das eine Frage der Programmierung? Sieht eher aus wie eine generische algorithmen-bezogene Frage.
- Es ist eine Programmier-Frage in dem Sinne, dass ich gerne die Lösung implementierbar in C++ zumindest 😉
- Keine Elemente eingefügt werden, die vorhandenen Elemente geändert werden.
- Es ist nicht O(n log n), ist dieses array bereits sortiert. Alles, was Sie tun müssen ist, tauschen Sie die Werte, bis Sie einen Wert gleich dem, den du erhöht. Schlimmste Szenario wäre O(n)
- Farshid Hinzugefügt habe ich einige code, ich denke, mehr oder weniger deinen Anforderungen entspricht. Ich sage es im Kommentar, denn es war update zu begraben beantworten.
- Ich habe einige code, den man sich anschauen kann.
- Danke Jungs für so viele Antworten! Sie sind alle Super 🙂
- [diese ignorieren. Ich dachte, Sie bedeutete für das Anhängen eines neuen Elements, nicht Schrittweite ein vorhandenes Element.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Habe ich noch nicht gearbeitet, dies vollständig, aber ich denke, die Allgemeine Idee, die helfen könnte, für ganze zahlen zumindest. Auf Kosten von mehr Speicher, können Sie pflegen eine separate Daten-Struktur, die behauptet, das Ende der index einer Folge von wiederholten Werten (da der Sie Sie vertauschen möchten Ihre erhöhte Wert mit der Endung-index der wiederholte Wert). Dies ist, weil es mit wiederholten Werten, dass Sie in den schlimmsten Fall
O(n)
Laufzeit: angenommen, Sie haben[0, 0, 0, 0]
und Sie erhöhen die Wertschöpfung am Standort0
. Dann ist esO(n)
zu finden, aus der letzten Position (3
).Aber lassen Sie uns sagen, dass Sie pflegen die Daten-Struktur, die ich erwähnt (eine Karte funktioniert, weil es hat
O(1)
- lookup). In diesem Fall müssten Sie so etwas wie dieses:So haben Sie einen Lauf von
0
Werte, die enden an Ort3
. Wenn Sie erhöhen einen Wert, sagen wir am Standorti
Sie überprüfen, um zu sehen, ob der neue Wert größer ist als der Wert, beii + 1
. Wenn es nicht, Sie sind in Ordnung. Aber wenn es ist, Sie schauen, um zu sehen, ob dort ein Eintrag für diesen Wert in der Sekundär-Daten-Struktur. Wenn nicht, können Sie einfach tauschen. Wenn es ist einen Eintrag, schaut Euch die Endung-index und dann tauschen mit dem Wert an dieser Position. Sie dann änderungen vornehmen, die Sie benötigen, um die sekundären Daten-Struktur entsprechend den neuen Zustand des Arrays.Gründlicher Beispiel:
Die sekundären Daten-Struktur ist:
Sagen wir, Sie erhöhen die Wertschöpfung am Standort
2
. So haben Sie erhöht3
zu4
. Das array sieht jetzt wie folgt aus:Schauen Sie auf das nächste element, das
3
. Dann mal bis der Eintrag für das element in der Sekundär-Daten-Struktur. Der Eintrag ist4
, was bedeutet, dass es ein run-of -3
's, die Ende an4
. Dies bedeutet, dass Sie können, tauschen Sie den Wert von der aktuellen Position mit dem Wert bei index4
:Nun müssen Sie auch zum aktualisieren der sekundären Daten-Struktur. Insbesondere, da der Lauf der
3
's endet ein index früh, so dass Sie brauchen, um zu Dekrementieren diesen Wert:Andere überprüfung, die Sie tun müssen, ist, um zu sehen, wenn der Wert wiederholt sich nicht mehr. Sie können es überprüfen, indem man die
i - 1
th und diei + 1
th Orte, um zu sehen, wenn Sie die gleiche wie der Wert in Frage. Wenn weder gleich sind, dann Sie können entfernen Sie den Eintrag für diesen Wert von der Karte.Wieder, dies ist nur eine Allgemeine Idee. Ich habe es code aus um zu sehen, ob es klappt wie ich dachte.
Bitte fühlen Sie sich frei, um poke Löcher.
UPDATE
Habe ich eine Implementierung dieses Algorithmus hier in JavaScript. Ich verwendet, JavaScript nur so konnte ich es schnell tun. Auch, weil ich codiert es sich ziemlich schnell, es kann vermutlich gereinigt werden. Ich habe die Kommentare allerdings. Ich bin mir nicht irgendetwas esoterisches, also das sollte einfach portierbar sein, um C++.
Gibt es im wesentlichen zwei Teile des Algorithmus: das Inkrementieren und austauschen (falls erforderlich), und der Buchführung erfolgt auf der Karte, die Spur hält unser Ende den Indizes läuft der wiederholten Werte.
Den code enthält eine Test-harness, beginnt mit einer Reihe von Nullen und Schritten zufälligen Positionen. Am Ende jeder iteration gibt es einen test, um sicherzustellen, dass das array sortiert ist.
3 -> x, 4 -> y, 5 -> z
, wie schnell finden Sie das paar mit der 1. Komponente5
? Haben Sie nicht zu tun einO(log n)
lookup auf Ihrer Liste von Paaren?O(1)
. Es ist nicht eine Liste von Paaren, sondern eine Karte, wo der Wert ist kodiert, um den Ende-index in einer Auflage von wiederholten Werten. Also lookup wird stetsO(1)
da Sie suchen nach Wert.O(1)
es sei denn, Sie sind den Umgang mit Kollisionen.map
ist O(log n), aber Sie könnenunordered_map
für O(1).map
undordered_map
, da letztere scheint ein besonderer Fall vonmap
. 🙂O(lg(n)+(k/2))
wok
ist die Anzahl der vorkommen eines wiederholten Wert.Nicht. Gegeben ein array von 0:
[0, 0, 0, 0, 0]
. Wenn Sie erhöhen Sie den ersten Wert, indem[1, 0, 0, 0, 0]
, dann haben Sie, um 4-swaps, um sicherzustellen, dass es bleibt sortiert.Gegeben ein sortiertes array ohne Duplikate, dann ist die Antwort ja. Aber nach der ersten operation (d.h. das erste mal, wenn Sie den Inkrement), dann könnten Sie möglicherweise Duplikate. Die weitere Schritten, die Sie tun, desto höher die Wahrscheinlichkeit ist, dass müssen Sie die Duplikate, und desto wahrscheinlicher ist es O(n) zu halten, das array sortiert.
Wenn alle Sie haben, ist das array, ist es unmöglich zu garantieren, die weniger als O(n) Zeit pro Inkrement. Wenn das, was du suchst, ist eine Datenstruktur, die unterstützt sortiert und lookup index, dann haben Sie wahrscheinlich wollen eine um stastic Baum.
O(n)
mit der einzigen array im schlimmsten Fall. Aber ich würde nicht sagen, dass es unmöglich, wenn diese Einschränkung ist nicht angegeben; Sie können einen Sekundär-Daten-Struktur.unordered_map
dann können Sie es immer noch tun in konstanter Zeit. Es steht nirgends, dass Sie am Ende tut es inO(n)
. Auch für das Gedächtnis, im schlimmsten Fall müssen Sien/2
Einträge in der map.Wenn die Werte klein sind, zählen, Sortieren, arbeiten wird. Stellen Sie das array
[0,0,0,0]
als{4}
. Die Inkrementierung der null gibt{3,1}
: 3 Nullen und eine eins. Im Allgemeinen erhöhen jeder x-Wert abziehen eines aus der Zählung von x und erhöht die Anzahl von {x+1}. Die flächeneffizienz ist O(N), obwohl, wo N ist der höchste Wert.O(1)
. Wenn Sie{3,1,2,4}
, und Sie möchten, erhöhen Sie den 5. index, würden Sie brauchen, um zu arbeiten, es ist die 2, die Bedürfnisse der Inkrementierung.{ 0,0,0,1,2,2,3,3,3,3 }
damit Sie wissen, in O(1), die Sie aktualisieren müssen Sie eine 2. Da haben Sie 6 zahlen, die kleiner oder gleich 6 ist, Sie können dann Inkrement der 6. (!) erstellen{ 0,0,0,1,2,3,3,3,3,3 }
. Wissend, dass Sie 6 zahlen, die kleiner oder gleich 2 bedeutet, halten eine partielle Summe von {3,1,2,4}, wobei wieder O(1) für Einzel-Schritten.Es hängt davon ab, wie viele Elemente den gleichen Wert haben können. Wenn mehrere Elemente den gleichen Wert haben können, dann ist es nicht möglich, O(1) mit normalen arrays.
Machen wir ein Beispiel: angenommen, array[5] = 21, und Sie wollen tun, array[5]++:
Erhöhen Sie den Artikel:
(was ist O(1) weil es ein array ist).
So, nun array[5] = 22.
Überprüfen Sie den nächsten Punkt (D. H., array[6]):
Wenn array[6] == 21, dann haben Sie zu halten überprüfung der neuen Einträge (D. H., array[7] und so weiter) , bis Sie einen höheren Wert als 21. An diesem Punkt können Sie die swap-Werte. Diese Suche ist nicht O(1), weil möglicherweise müssen Sie Scannen Sie das gesamte array.
Statt, wenn der Artikel nicht den gleichen Wert haben, dann haben Sie:
Erhöhen Sie den Artikel:
(was ist O(1) weil es ein array ist).
So, nun array[5] = 22.
Den nächsten Punkt nicht 21 (weil zwei Objekte können nicht den gleichen Wert haben), also muss es einen Wert > 21 und das array bereits sortiert.
So nehmen Sie sortierte array und hashtable. Sie gehen über ein array, um herauszufinden, "flacher" Bereiche, in denen Elemente mit dem gleichen Wert. Für jedes flache Gebiet, die Sie haben, um herauszufinden, drei Dinge 1) wo es beginnt (index des ersten Elements) 2) was ist es Wert 3) was ist der Wert des nächsten Elements (die nächst größeren). Dann setzen Sie dieses Tupel in die Hash-Tabelle, wo die Schlüssel werden element Wert. Dies ist Voraussetzung, und es ist Komplexität eigentlich egal.
Dann, wenn Sie erhöhen einige element (index i) Sie look-up-Tabelle für den index der nächsten größeren element (nennen wir ihn j) und swap
i
miti - 1
. Dann 1) fügen Sie einen neuen Eintrag in der Hashtabelle vorhanden 2) update-Eintrag, für die es in den früheren Wert.Mit perfekten Hashtabelle (oder begrenzten Bereich der möglichen Werte) es wird fast O(1). Der Nachteil: es wird nicht stabil sein.
Hier einige code:
Ja und Nein.
Ja, wenn die Liste enthält nur eindeutige Ganzzahlen, da das bedeutet, dass Sie nur überprüfen müssen, um den nächsten Wert. Nicht in jeder anderen situation. Wenn die Werte nicht eindeutig sind, inkrementiert die erste N doppelte Werte bedeutet, dass Sie es verschieben müssen N Positionen. Wenn die Werte sind Gleitkommazahlen, Sie können Tausende von Werte zwischen x und x+1
Ist es wichtig, sehr klar über die Anforderungen, ist der einfachste Weg, um auszudrücken, das problem als ADT (Abstrakter Datentyp), Auflistung der erforderlichen Vorgänge und Komplexität.
Hier ist, was ich denke, du suchst: ein Datentyp bietet die folgenden Operationen:
Construct(n)
: Erstellen Sie ein neues Objekt von der Größen
alle, deren Werte0
.Value(i)
: Gibt den Wert an indexi
.Increment(i)
: Erhöhen Sie den Wert bei indexi
.Least()
: Return der index des Elements mit dem geringsten Wert (oder ein solches element, falls es mehrere gibt).Next(i)
: Return der index des nächsten Elements nach dem elementi
in eine sortierte Traversierung beginnend beiLeast()
, so dass die überquerung zurück jedes element.Abgesehen von den Konstruktor, wir möchten, dass jeder der oben genannten Vorgänge zu haben, die Komplexität
O(1)
. Wir wollen auch das Objekt zu besetzenO(n)
Raum.Die Implementierung verwendet eine Liste der Gruppen; jede Gruppe hat eine
value
und eine Liste von Elementen. Jedes element hat einen index, einen Zeiger, um den Eimer es gehört. Schließlich haben wir ein array von Zeigern auf Elemente. (In C++, ich würde wahrscheinlich verwenden Sie Iteratoren anstelle von Zeigern; in einer anderen Sprache, würde ich wahrscheinlich aufdringlich Listen.) Die Invarianten sind, dass keine Eimer ist immer leer, und dievalue
der Eimer sind streng monoton Steigend.Beginnen wir mit einem einzigen Eimer mit dem Wert 0, welches eine Liste von
n
Elemente.Value(i)
umgesetzt wird-auch durch Rücksendung der Wert der Eimer des Elements wird durch den iterator auf elementi
des Arrays.Least()
ist der index des ersten Elements in der ersten Eimer.Next(i)
ist der index des nächsten Elements nach der einen wird durch den iterator auf elementi
, es sei denn, dass der iterator wird jetzt schon darauf am Ende der Liste, in dem Fall ist es das erste element in der nächsten Eimer, es sei denn, das element der Eimer ist der Letzte Eimer, in dem Fall sind wir am Ende der element-Liste.Die einzige Schnittstelle, die von Interesse ist
Increment(i)
, die ist wie folgt:Wenn das element
i
ist das einzige element in Ihre Eimer ist (d.h. es gibt kein Nächstes element in der Liste Eimer, und elementi
ist das erste element in der Liste Eimer):O(1)
, unabhängig von der Liste die Größe, denn es ist nur ein Zeiger tauschen), und löschen Sie dann den nächsten Eimer.Wenn das element
i
ist nicht das einzige element in Ihre Eimer, dann:i
auf den nächsten bucket-Liste.i
aus und fügen Sie es zwischen dem Eimer und der nächste.nur die Iteration entlang der array aus dem geänderten element, bis Sie die richtige Stelle, dann tauschen. Average-case-Komplexität ist O(N) wobei N die Durchschnittliche Anzahl der Duplikate. Worst-case ist O(n), wobei n die Länge des Arrays. So lang wie N ist nicht groß und nicht skaliert schlecht mit n, bist du gut und kann wohl behaupten es ist O(1) für praktische Zwecke.
Wenn Duplikate sind die norm und/oder skalieren stark mit n, dann gibt es bessere Lösungen, siehe andere Antworten.
Ich denke, dass es möglich ist, ohne Verwendung einer hashtable. Ich habe eine Implementierung hier: