Ordina array intero in tempo strettamente O (n)

Question

Mi è stata posta questa domanda nell'intervista di recente.

Dato un array intero ordinato contenente numeri negativi e positivi, come ricorrere all'array in base ai valori assoluti degli elementi?

Questo deve essere eseguito rigorosamente nel tempo O (n).

ingresso

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

uscita

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

Quali sono le possibili soluzioni oltre al tempo O (n)?

Answer 1

Fondamentalmente, avremo 2 teste, una che guarda alla fine della matrice, una all'inizio.

Confrontiamo il valore assoluto delle 2 voci a cui puntano le nostre teste e inseriamo il più grande nel nostro nuovo array ordinato. Quindi qui sarebbe 14.

New array: {14} 

Quindi spostiamo la testa di qualsiasi oggetto selezionato più vicino al centro. Così qui ci spostiamo la nostra testa che punta al 14 per 8.

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

Abbiamo poi ripetere il processo, inserendo il più grande dei 2 valori assoluti in l'inizio della nostra nuova, array ordinato.Qui sarebbe -9, come | -9 | > | 8 |

New array: {-9, 14} 

E dopo ci si sposta di nuovo la testa:

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

Ripetere fino a quando entrambe le teste si incontrano nel centro

Answer 2

Prendiamo il tuo esempio:

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

Si potrebbe riscrivere questo in due parti:

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

due osservazioni ovvie:

• La parte sinistra è ordinato decrescente
• La parte destra è ordinata in ordine crescente

Ora si fondono semplicemente questi due subarrays ordinati, che è probabilmente in tempo lineare. Dai un'occhiata all'algoritmo qui How to merge two sorted arrays into a sorted array?.

Poiché non si dispone di questi array divisi, si trova il punto nell'array che converte il negativo in positivo. Da quel punto di divisione, puoi andare indice per indice fino ai limiti dell'array e ricostruire di nuovo un array ordinato.

Answer 3

Come accennato nei commenti, si sono fondamentalmente alla ricerca di un merge sort. I dati originali sono già ordinati, quindi tutto ciò che devi fare è recuperare i valori in ordine da ciascuno degli insiemi di numeri negativi e positivi, unendoli in base ai loro valori assoluti.

Il codice dovrebbe essere simile a questo:

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++]; 
    } 
} 

Quanto sopra è secondo me un po 'più facile da afferrare, ma come un'altra risposta fa notare, lo si può fare senza nemmeno la scansione al 0-point dei dati , ordinando dall'altra parte. Il codice per questo sarebbe simile a questa:

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++]; 
    } 
}