Matrice con valori specifici

Question

Data una matrice la dimensione di n dove: 1/2 della matrice è con un valore singolo (sconosciuto). 1/4 della matrice è con un singolo valore (sconosciuto) diverso. E così via per 1/8, 1/16, 1/32 Fornire un algoritmo per ordinare l'array. Non è possibile utilizzare l'algoritmo mediana trovare

Quindi quello che ho pensato è: Ci sono solo valori logn diversi C'è una soluzione semplice utilizzando un heap binario su O (n * loglogn) Sembra una domanda che aveva bisogno da risolvere in O (n)

Answer 1

L'idea è quella di utilizzare l'algoritmo maggioranza che prende O (n) allora scoprire che cosa è il valore "metà" di eliminarlo dalla matrice e poi farlo di nuovo su il nuovo array n + n/2 + n/4 + n/8 + ..... < 2n => O (n)

Answer 2

Ecco un possibile approccio:

• scansione delle frequenze elemento dell'array e memorizzare (ci sono log n elementi distinti) di una tabella hash in amortized O (n) ; questo è fattibile perché we can do insertions in amortized O(1) time;
• ora eseguire un algoritmo di ordinamento classico su questi elementi di registro n: questo è eseguibile in tempo deterministico O (log n log log n) utilizzando, ad esempio, heap sort o merge sort;
• ora espandere l'array ordinato --- o crearne uno nuovo e riempirlo usando l'array ordinato e la tabella hash --- usando le frequenze dalla tabella hash; questo è fattibile nel tempo ammortizzato O (n).

L'intero algoritmo funziona quindi in tempo O (n) ammortizzato, cioè è dominato dall'eliminazione di duplicati e dall'espansione dell'array ordinato. La complessità spaziale è O (n).

Questo è essenzialmente ottimale perché è necessario "toccare" tutti gli elementi per stampare l'array ordinato, il che significa che abbiamo un limite inferiore corrispondente di Omega (n) sul tempo di esecuzione.

Answer 3

Passando sopra l'array una volta, mantenere la mappa hash per i valori visualizzati. Come hai detto tu ci sono solo log(n) valori diversi.

Ora avete elenco di tutti i diversi valori - l'ordinamento li porterà lon(n)*log(log(n))

Una volta che hai i uniq ordinati come è facile constract l'array originale: il valore massimo avrà n/2 cellule, il 2 ° prendere n/4 e così via.

Il tempo di esecuzione totale è O(n + lon(n)*log(log(n)) + n) che è O(n)