Encuentra el número N-ésimo más frecuente en la matriz

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

Creo que podemosEncuentra el número N-ésimo más frecuente en la matriz

(i) almacenar la aparición de cada elemento utilizando mapas en C++

(ii) construir un Max-heap en tiempo lineal de las ocurrencias (o frecuencia) del elemento y luego extraer hasta el elemento N-ésimo, Cada extracción toma el tiempo de registro (n) para heapify.

(iii) obtendremos la frecuencia de la N-ésimo número más frecuente

(iv) entonces podemos lineal búsqueda entre los hash para encontrar el elemento que tiene esta frecuencia.

Tiempo - O (NlogN) espacio - O (N)

¿Hay algún método mejor?

Fuente

2012-06-10 Luv

Ver [Selección Algoritmo] (http://en.wikipedia.org/wiki/ Selection_algorithm) que permite seleccionar el Nth element from y unordered array en O (N). – salva

@salva - La pregunta es seleccionar n-ésimo número más FREQUENCY y no enésimo elemento. – user754657

@ user754657: sí, todavía se requiere el paso * i *, pero los pasos * ii *, * iii * y * iv * pueden reemplazarse por el algoritmo de selección que es O (N), dando como resultado una solución que es O (N) a nivel mundial. – salva

Su método es básicamente correcto. Evitaría la búsqueda de hash final si marca cada vértice del montón construido con el número que representa. Además, es posible vigilar constantemente el quinto elemento del montón mientras lo estás construyendo, porque en algún momento puedes llegar a una situación en la que el resultado ya no puede cambiar y el resto del cálculo se puede descartar. Pero esto probablemente no haría que el algoritmo sea más rápido en el caso general, y tal vez ni siquiera en casos especiales. Entonces respondiste tu propia pregunta correctamente.

Fuente

2012-06-10 02:37:55

Depende de si desea el método más efectivo o más fácil de escribir.

1) si sabe que todos los números serán de 0 a 1000, simplemente haga una matriz de 1000 ceros (ocurrencias), recorra su matriz e incremente la posición correcta de ocurrencia. Luego ordena estas ocurrencias y selecciona el valor Nth.

2) Tiene una "bolsa" de artículos únicos, recorre sus números, verifique si ese número está en una bolsa, si no, lo puede agregar, si está aquí, simplemente incrementa el número de ocurrencias . Luego, eliges un N-ésimo número más pequeño.

La bolsa puede ser lineal, BST o Dictionary (tabla hash).

La pregunta es "N-th más frecuente", por lo que creo que no puede evitar la clasificación (o estructura de datos inteligente), por lo que la mejor complejidad no puede ser mejor que O (n * log (n)).

Fuente

2012-06-10 02:32:30

El método 1 no es realmente aplicable, ya que el rango de número no tiene un límite. En el método 2, el pick n-ésimo más pequeño se puede hacer en la complejidad de tiempo promedio O (K) (donde K es el número de elementos únicos) con el algoritmo de selección: STL 'algorithm' función' nth_element'. La "bolsa" puede ser 'map' de STL como lo ha mencionado el OP (STL' map' es mejor que BST normal, ya que 'map' se implementa como árbol auto equilibrado). – nhahtdh

nhahtdh: Elegir la N-ésima más pequeña de los números K no se puede hacer en O (K). Al menos debe clasificarlos o recorrerlos con un montón de N elementos ... que es la "bolsa" de la que estaba hablando. –

Si solo busca "nth element" o "selection algorithm", verá lo que quiero decir. – nhahtdh

Se puede hacer en tiempo y espacio lineal. Deje T ser el número total de elementos en la matriz de entrada desde la cual tenemos que encontrar el enésimo número más frecuente:

Cuente y almacene la frecuencia de cada número en T en un mapa. Deje M ser la cantidad total de elementos distintos en la matriz. Entonces, el tamaño del mapa es M. - O (T)
Encuentra la frecuencia más grande N en el mapa usando Selection algorithm. - O (M)

tiempo Total = O (T) + O (M) = O (T)

Fuente

2012-08-01 13:15:37 Garima

Encuentra el número N-ésimo más frecuente en la matriz

Respuesta

Cuestiones relacionadas