Stolperte über diese Interviewfrage. Gegeben sei ein Array der Größe n, wo das erste n / 2 sortiert ist und die zweite Hälfte ist sortiert. Sortieren Sie das gesamte Array an Ort und Stelle. Nun, was ich an Ort und Stelle denken kann, ist etwas wie Einfügungssortierung, die Raumkomplexität als O (1) haben wird, aber die Zeitkomplexität wird mehr als O (n) sein. Ist eine O (n) -In-situ-Lösung für dieses Problem möglich?
Habe zwei (logische) Zeiger - lasst sie x und y nennen. x zeigt auf das erste Element der ersten n / 2 Elemente. y zeigt auf das erste Element der zweiten n / 2 Elemente.
Wenn das Element bei y kleiner ist als dasjenige bei x (nennen wir n (y) und n (x)), dann füge n (y) bei x ein und inkrementiere x & amp; y um 1. Andernfalls wird x um 1 erhöht und erneut überprüft. Sobald Sie auf "n" drücken, halten Sie y an und wiederholen Sie die Schritte bis x == y.
z. B.
%Vor%Um zwei bereits sortierte Listen zu sortieren, würden Sie normalerweise merge sort verwenden; Der einfachste Weg wäre, eines der halben Arrays irgendwo zu kopieren. Das ist nicht vorhanden, aber funktioniert.
Das Tauschen von Elementen funktioniert nicht, da es nicht garantiert, dass der Maximalwert der ersten Hälfte des Arrays kleiner ist als der Minimalwert in der rechten Hälfte:
%Vor%swap i = 0, j = 3
%Vor%swap i = 1, j = 5
%Vor%Wenn Sie dies durch weiteres Austauschen beheben, erhalten Sie eine O (N ^ 2) Bubble-Sortierung.