Buscar qué números aparecen más en un vector

Tengo algunos números almacenados en un vector. Quiero encontrar qué número aparece más en el vector.Buscar qué números aparecen más en un vector

¿Hay algún algoritmo fácil/rápido (STL o lo que sea) que hace esto?

Fuente

2010-03-21 VaioIsBorn

Consulte preguntas como: http://stackoverflow.com/questions/1204313/counting-occurences-in-a-vector, http://stackoverflow.com/questions/2184336/how-to-get-the-most -representada-objeto-de-un-array – outis

Ordénelo, luego repítalo y mantenga un contador que incremente cuando el número actual sea el mismo que el número anterior y restablezca a 0 de lo contrario. También realice un seguimiento de cuál fue el valor más alto del contador hasta el momento y cuál fue el número actual cuando se alcanzó ese valor. Esta solución es O(n log n) (debido a la clasificación).

Como alternativa, puede usar un hashmap de int a int (o si conoce los números dentro de un rango limitado, puede usar una matriz) e iterar sobre el vector, aumentando the_hashmap[current_number] en 1 para cada número. Luego itere a través del hashmap para encontrar su valor más grande (y la clave que le pertenece). Sin embargo, esto requiere una estructura de datos hashmap (a menos que pueda usar matrices que también serán más rápidas), que no es parte de STL.

Fuente

2010-03-21 22:14:20 sepp2k

Solo para agregar lo obvio, para ordenar usando el tipo de STL: http://www.cplusplus.com/reference/algorithm/sort/ –

@ Steve314: unordered_map estará en el próximo estándar. No está en el estándar 2003 (es decir, actual). – sepp2k

Wierd - De alguna manera tuve la idea de que TR1 era la "primera revisión de texto" de 2003. – Steve314

Esta es la forma en que lo hice:

int max=0,mostvalue=a[0]; 
    for(i=0;i<a.size();i++) 
    { 
     co = (int)count(a.begin(), a.end(), a[i]); 
     if(co > max) 
     {  max = co; 
       mostvalue = a[i]; 
     } 
    }

Sólo que no sé lo rápido que es, es decir, O()? Si alguien pudiera calcularlo y publicarlo aquí, estaría bien.

Fuente

2010-03-21 22:25:50 VaioIsBorn

Es O (n * n), por lo que no es el método más eficiente, pero es de solo lectura y no requiere almacenamiento adicional si eso es importante. –

Esto es O (n^2), porque cada vez que llamas cuenta, mira cada elemento en el vector. Se puede hacer en O (n) (http://stackoverflow.com/questions/512590/computing-the-statistical-mode/512601#512601) –

Si se quiere evitar la clasificación v su vector, utilizar un mapa:

int max = 0; 
int most_common = -1; 
map<int,int> m; 
for (vi = v.begin(); vi != v.end(); vi++) { 
    m[*vi]++; 
    if (m[*vi] > max) { 
    max = m[*vi]; 
    most_common = *vi; 
    } 
}

Esto requiere más memoria y tiene un tiempo de ejecución esperado muy similar. La memoria requerida debe estar en el orden de una copia vectorial completa, menos si hay muchas entradas duplicadas.

Fuente

2010-03-21 22:58:10 tucuxi

Buscar qué números aparecen más en un vector

Respuesta

Cuestiones relacionadas