Suche nach eindeutigen Zahlen aus sortierten Arrays in weniger als O (n)

Teilen und erobern :

• sehen Sie sich das erste und letzte Element einer sortierten Sequenz an (die ursprüngliche Sequenz ist data[0]..data[data.length-1] ).
• Wenn beide gleich sind, ist das einzige Element in der Sequenz das erste (egal wie lang die Sequenz ist).
• Wenn die Werte unterschiedlich sind, teilen Sie die Sequenz und wiederholen Sie sie für jede Teilsequenz.

Löst in O (log (n)) im durchschnittlichen Fall und O (n) nur im schlimmsten Fall (wenn jedes Element anders ist).

Java-Code:

Ich denke nicht, dass es in weniger als O (n) gemacht werden kann. Nehmen wir den Fall, in dem das Array 1 2 3 4 5 enthält: Um die korrekte Ausgabe zu erhalten, müsste jedes Element des Arrays betrachtet werden, daher O (n).

Wenn das sortierte Array der Größe n m distinct Elemente hat, können Sie O(mlogn) .

Beachten Sie, dass dies effizient wird, wenn m << n (eg m=2 and n=100)

Algorithmus:

Initialisierung: Aktuelles Element y = first element x[0]

Schritt 1: Suche eine binäre Suche nach dem letzten Vorkommen von y in x (kann in O(log(n)) time gemacht werden. Lassen Sie den Index i

Schritt 2: y = x[i+1] und gehe zu Schritt 1

Edit: In Fällen wo m = O(n) wird dieser Algorithmus schlecht funktionieren. Um es zu verbessern, können Sie es parallel zum regulären Algorithmus O(n) ausführen. Der Meta-Algorithmus besteht aus meinem Algorithmus und O(n) -Algorithmus, die parallel laufen. Der Meta-Algorithmus stoppt, wenn einer dieser beiden Algorithmen abgeschlossen ist.

Da die Daten aus Ganzzahlen bestehen, gibt es eine endliche Anzahl eindeutiger Werte, die zwischen zwei beliebigen Werten auftreten können. Beginnen Sie also mit dem ersten und letzten Wert im Array. Wenn a[length-1] - a[0] < length - 1 , gibt es einige sich wiederholende Werte. Setzen Sie a[0] und a[length-1] in einen Container mit konstanter Zugriffszeit wie einen Hash-Satz. Wenn die beiden Werte gleich sind, können Sie davon ausgehen, dass nur ein eindeutiger Wert im Array vorhanden ist und Sie fertig sind. Sie wissen, dass das Array sortiert ist. Wenn also die beiden Werte unterschiedlich sind, können Sie jetzt das mittlere Element betrachten. Wenn das mittlere Element bereits in der Menge der Werte ist, wissen Sie, dass Sie den gesamten linken Teil des Arrays überspringen und nur den rechten Teil rekursiv analysieren können. Andernfalls analysieren Sie den linken und rechten Teil rekursiv.

Abhängig von den Daten im Array können Sie die Menge aller eindeutigen Werte in einer anderen Anzahl von Operationen erhalten. Sie erhalten sie in konstanter Zeit O(1) , wenn alle Werte gleich sind, da Sie es erst nach dem Überprüfen des ersten und letzten Elements wissen. Wenn es "relativ wenige" eindeutige Werte gibt, liegt Ihre Komplexität nahe bei O(log N) , weil Sie nach jeder Partition "ziemlich oft" mindestens die Hälfte des analysierten Sub-Arrays wegwerfen können. Wenn die Werte alle eindeutig sind und a[length-1] - a[0] = length - 1 , können Sie die Menge auch in konstanter Zeit definieren, da sie fortlaufende Nummern von a[0] bis a[length-1] sein müssen. Um sie jedoch tatsächlich aufzulisten, müssen Sie jede Zahl ausgeben, und es gibt N davon.

Vielleicht kann jemand eine formellere Analyse liefern, aber ich schätze, dass dieser Algorithmus in der Anzahl der eindeutigen Werte eher linear ist als in der Größe des Arrays. Dies bedeutet, dass, wenn es wenige eindeutige Werte gibt, Sie sie in wenigen Operationen auch für ein großes Array erhalten können (z. B. in konstanter Zeit, unabhängig von der Array-Größe, wenn nur ein eindeutiger Wert vorhanden ist). Da die Anzahl der eindeutigen Werte nicht größer ist als die Größe des Arrays, behaupte ich, dass dies diesen Algorithmus "besser als O (N)" macht (oder streng: "nicht schlechter als O (N) und in vielen Fällen besser"). ).