Ordina una matrice in un ordine specifico - non crescente / decrescente

• Inserisci tutti gli elementi di a in un albero di ricerca binaria autobilanciante (BST) - O (n log n)

• Per ogni elemento di w , cerca e rimuovi l'elemento più vicino nel BST e aggiungilo all'output - O (n log n)

  Trovare l'elemento più vicino in una BST è piuttosto facile. Se l'elemento è maggiore dell'elemento del nodo corrente, guarda a destra, se è più piccolo, guarda a sinistra, se è uguale, fermati. Mentre scendi dall'albero, tieni semplicemente traccia dell'elemento più vicino.

Avere restituisce gli indici anziché l'elemento dovrebbe essere banale.

Tempo di esecuzione totale - O (n log n)

Funzionerebbe? Ordina entrambi gli array numericamente, ricordando gli indici originali di w in modo da poterli ripristinare rapidamente. Quindi usa l'unsort di w su a. Questo ti darebbe un risultato di {2, 3, 1, 0} piuttosto che {2, 3, 0, 1}, ma che potrebbe essere una risposta migliore, a seconda di come la guardi, e sarebbe un po 'più veloce di forzarlo bruto.

Diamo un'occhiata all'array di esempio a:

a = {5.5, 6.5, 2.4, 3.1}

Ora sappiamo che per qualsiasi numero x < 2,75 il numero più vicino in quella matrice sarà 2,4 (a indice 2). Allo stesso modo, per ogni numero x, 2,75 < x < 4.3, il numero più vicino in quella matrice sarà 3.1 (all'indice 3), e così via:

upper limit        index
2.75               2
4.3                3
6.0                0
"+infinity"        1

Ora, usare questa tabella per trovare il numero più vicino in a per w [0] = 1 è facile. Trova il limite superiore più vicino per 1, che è 2,75 e l'indice corrispondente dell'array a è 2. (Questo può essere ottimizzato usando la ricerca binaria.)

Poiché tale indice può essere utilizzato solo una volta, ora dobbiamo modificare la tabella rimuovendo quella voce:

upper limit        index
4.3                3
6.0                0
"+infinity"        1

Successivamente, il limite superiore più vicino per w [1] = 2 è 3 e dopo aver rimosso la tabella appare come segue:

upper limit        index
6.0                0
"+infinity"        1

Dopo il passo successivo (w [2] = 6) la tabella ha una sola voce:

upper limit        index
"+infinity"        1

In questo esempio non è stato necessario rimuovere l'ultima voce dalla tabella durante il processo. Se è necessario, l'ultima voce della tabella risultante deve essere aggiornata per avere il limite superiore di "+ infinito".

NOTA: non ho controllato se questo algoritmo funzioni effettivamente!