Trovare il numero N-esimo più frequente nella matrice

Question

Find the nth most frequent number in array. 
(There is no limit on the range of the numbers) 

Penso che possiamo

(i) memorizzare il verificarsi di ogni elemento utilizzando le mappe in C++

(ii) costruire un Max-heap nel tempo lineare delle occorrenze (o frequenza) dell'elemento e quindi estrae fino all'elemento N-esimo, Ogni estrazione richiede log (n) il tempo di heapify.

(iii) avremo la frequenza del N-esimo numero più frequente

(iv) allora possiamo lineare ricerca tra l'hash per trovare l'elemento avente questa frequenza.

Tempo - O (N log N) Space - O (N)

Esiste un metodo migliore?

Answer 1

Il tuo metodo è fondamentalmente corretto. Eviterai la ricerca di hash finale se contrassegni ciascun vertice dell'heap costruito con il numero che rappresenta. Inoltre, è possibile tenere costantemente sotto osservazione il quinto elemento del mucchio mentre lo si sta costruendo, perché a un certo punto si può arrivare a una situazione in cui il risultato non può più cambiare e il resto del calcolo può essere eliminato. Ma questo probabilmente non renderebbe l'algoritmo più veloce nel caso generale, e forse nemmeno in casi particolari. Quindi hai risposto correttamente alla tua domanda.

Answer 2

Dipende dal metodo più efficace o più facile da scrivere.

1) se si sa che tutti i numeri saranno compresi tra 0 e 1000, basta creare una serie di 1000 zeri (occorrenze), scorrere l'array e incrementare la posizione di occorrenza corretta. Quindi ordinate queste occorrenze e selezionate il valore Nth.

2) Hai una "borsa" di articoli unici, fai un giro tra i numeri, controlla se quel numero è in una borsa, in caso contrario, lo aggiungi, se è qui, basta incrementare il numero di occorrenze . Quindi scegli un n ° numero più piccolo da esso.

Borsa può essere array lineare, BST o Dizionario (tabella hash).

La domanda è "N-esimo più frequente", quindi penso che non è possibile evitare l'ordinamento (o la struttura dei dati intelligente), quindi la migliore complessità non può essere migliore di O (n * log (n)).

Answer 3

Può essere eseguito in tempo e spazio lineari. Sia T il numero totale di elementi nell'array di input da cui dobbiamo trovare il numero N ° più frequente:

1. Contare e memorizzare la frequenza di ogni numero in T in una mappa. Sia M il numero totale di elementi distinti nella matrice. Quindi, la dimensione della mappa è M. - O (T)
2. Trova l'ennesima frequenza nella mappa utilizzando Selection algorithm. - O (M)

Tempo totale = O (T) + O (M) = O (T)