Sortierung Integer-Array in streng O (n) Zeit

Question

Ich wurde diese Frage im Interview vor kurzem gestellt.

Bei einem sortierten Integer-Array, das negative und positive Zahlen enthält, wie wird das Array basierend auf absoluten Werten der Elemente verwendet?

Dies musste streng in O (n) Zeit durchgeführt werden.

Eingangs

{-9, -7, -3,1,6,8,14}

Output

{1, -3,6, -7,8, -9,14}

Was sind die möglichen Lösungen außer O (n) Zeit?

Answer 1

Im Grunde werden wir 2 Köpfe haben, einer schaut auf das Ende des Arrays, einer am Anfang.

v     v 
{-9, -7, -3, 1, 6, 8, 14} 

Wir vergleichen den absoluten Wert der 2 Einträge unsere Köpfe zeigen und die größeren in unseren neuen, sortierte Array einzufügen. Also wäre es hier 14.

Wir bewegen dann den Kopf des ausgewählten Elements näher zum Zentrum. Also hier haben wir unseren Kopf bewegen, auf 14 zu zeigen 8.

v    v 
{-9, -7, -3, 1, 6, 8, 14} 

Wir wiederholen Sie den Vorgang, den größeren der zwei Absolutwerte in den Anfang unseres neuen, sortiert Array eingefügt wird.Hier wäre das -9, als | -9 | > | 8 |

New array: {-9, 14} 

Und nachdem wir den Kopf wieder bewegen:

 v   v   
{-9, -7, -3, 1, 6, 8, 14} 

wiederholen, bis beide Köpfe wie in der Mitte

Answer 2

Lassen Sie uns Ihr Beispiel nehmen:

{-9,-7,-3,1,6,8,14} 

Sie diese in zwei Teile umschreiben könnte:

{-9,-7,-3} and {1,6,8,14} 

Zwei offensichtliche Beobachtungen:

• Der linke Teil sortiert absteigend
• Der rechte Teil ist aufsteigend sortiert

Jetzt im Grunde nur diese beiden sortierten Subarrays zusammenführen, die möglicherweise in linearer Zeit ist. Hier finden Sie den Algorithmus How to merge two sorted arrays into a sorted array?.

Da diese Arrays nicht aufgeteilt sind, finden Sie den Punkt im Array, der negativ auf positiv umkehrt. Von diesem Splitpunkt aus können Sie Index für Index bis zu den Grenzen des Arrays gehen und ein sortiertes Array erneut rekonstruieren.

Answer 3

in den Kommentaren erwähnt treffen, die Sie suchen grundsätzlich bei einer Mergesort. 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 wie folgt aussehen:

int[] input = { -9, -7, -3, 1, 6, 8, 14 }; 
int[] output = new int[input.Length]; 
int negativeIndex, positiveIndex = 0, outputIndex = 0; 

while (input[positiveIndex] < 0) 
{ 
    positiveIndex++; 
} 

negativeIndex = positiveIndex - 1; 

while (outputIndex < output.Length) 
{ 
    if (negativeIndex < 0) 
    { 
     output[outputIndex++] = input[positiveIndex++]; 
    } 
    else if (positiveIndex >= input.Length) 
    { 
     output[outputIndex++] = input[negativeIndex--]; 
    } 
    else 
    { 
     output[outputIndex++] = -input[negativeIndex] < input[positiveIndex] ? 
      input[negativeIndex--] : input[positiveIndex++]; 
    } 
} 

Die obige IMHO ist etwas leichter zu begreifen, sondern als eine andere Antwort weist darauf hin, können Sie es tun, ohne auch nur das Scannen auf den 0-Punkt der Daten , indem man vom anderen Ende sortiert. Der Code für das wäre in etwa so aussehen:

int[] output = new int[input.Length]; 
int negativeIndex = 0, positiveIndex = input.Length -1, outputIndex = input.Length - 1; 

while (outputIndex >= 0) 
{ 
    if (input[negativeIndex] >= 0) 
    { 
     output[outputIndex--] = input[positiveIndex--]; 
    } 
    else if (input[positiveIndex] < 0) 
    { 
     output[outputIndex--] = input[negativeIndex++]; 
    } 
    else 
    { 
     output[outputIndex--] = -input[negativeIndex] < input[positiveIndex] ? 
      input[positiveIndex--] : input[negativeIndex++]; 
    } 
}