Ich wurde diese Frage kürzlich im Interview gestellt.
Wie wird das Array, basierend auf absoluten Werten von Elementen, in einem sortierten Integer-Array mit negativen und positiven Zahlen behandelt?
Dies musste streng in O (n) Zeit erfolgen.
Eingabe
{- 9, -7, -3,1,6,8,14}
Ausgabe
{1, -3,6, -7,8, -9,14}
Was sind die möglichen Lösungen außer O (n) Zeit?
Grundsätzlich werden wir zwei Köpfe haben, von denen einer auf das Ende des Arrays schaut, einer auf den Anfang.
%Vor%Wir vergleichen den absoluten Wert der 2 Einträge, auf die unsere Köpfe zeigen, und fügen den größeren Wert in unser neues, sortiertes Array ein. Also hier wäre es 14.
%Vor%Wir bewegen dann den Kopf des ausgewählten Gegenstandes näher zur Mitte. Hier bewegen wir unseren Kopf und zeigen auf 14 bis 8.
%Vor%Wir wiederholen dann den Vorgang, indem wir den größeren der 2 absoluten Werte in den Anfang unseres neuen, sortierten Arrays einfügen. Hier wäre das -9, als | -9 | & gt; | 8 |
%Vor%Und nachdem wir den Kopf wieder bewegen:
%Vor%Wiederholen Sie dies, bis sich beide Köpfe in der Mitte treffen.
Nehmen wir Ihr Beispiel:
%Vor%Sie könnten dies in zwei Teile umschreiben:
%Vor%Zwei offensichtliche Beobachtungen:
Nun fusionieren Sie diese beiden sortierten Subarrays einfach zusammen, was möglicherweise in linearer Zeit geschieht. Hier nach dem Algorithmus suchen Wie zwei sortiert zusammengeführt werden Arrays in ein sortiertes Array? .
Da diese Arrays nicht aufgeteilt sind, finden Sie den Punkt im Array, der negativ zu positiv wird. Von diesem Split-Punkt aus können Sie Index für Index bis zu den Grenzen des Arrays gehen und ein sortiertes Array erneut rekonstruieren.
Wie in den Kommentaren erwähnt, betrachten Sie grundsätzlich eine Zusammenführungssortierung. Die Originaldaten sind bereits sortiert, Sie müssen lediglich die Werte in der Reihenfolge von jeder der negativen und positiven Zahlengruppen abrufen und sie entsprechend ihren absoluten Werten zusammenführen.
Der Code würde etwa so aussehen:
%Vor%Das obige ist IMHO etwas leichter zu verstehen, aber wie eine andere Antwort darauf hinweist, können Sie es tun, ohne den Nullpunkt der Daten zu scannen, indem Sie vom anderen Ende aus sortieren. Der Code dafür würde ungefähr so aussehen:
%Vor%