Encontrar la frecuencia de los números en un grupo dado de números

Question

Supongamos que tenemos un vector / matriz en C ++ y deseamos contar cuál de estos N elementos tiene la mayor cantidad de repeticiones y generar la cuenta más alta. Qué algoritmo es el más adecuado para este trabajo.

ejemplo:

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

la salida es 4 porque 2 ocurre 4 veces. Esa es la cantidad máxima de veces que ocurre 2.

Answer 1

Ordene la matriz y luego haga un pase rápido para contar cada número. El algoritmo tiene una complejidad O (N * logN).

Alternativamente, cree una tabla hash, utilizando el número como clave. Almacene en la tabla hash un contador para cada elemento que haya introducido. Podrás contar todos los elementos en una sola pasada; sin embargo, la complejidad del algoritmo ahora depende de la complejidad de su función hasing.

Answer 2

Optimizado para espacio:

Quicksort (por ejemplo) luego itera sobre los elementos, haciendo un seguimiento de la cuenta más grande solamente. En el mejor de los casos O (N log N).

Optimizado para la velocidad:

Iterar sobre todos los elementos, haciendo un seguimiento de los recuentos por separado. Este algoritmo siempre será O (n).

Answer 3

Si tiene la RAM y sus valores no son demasiado grandes, use ordenación de conteo .

Answer 4

Una posible implementación de C ++ que hace uso de STL podría ser:

#include <iostream>
#include <algorithm>
#include <map>

// functor
struct maxoccur
{
    int _M_val;
    int _M_rep;

    maxoccur()
    : _M_val(0),
      _M_rep(0)
    {}

    void operator()(const std::pair<int,int> &e)
    {
        std::cout << "pair: " << e.first << " " << e.second << std::endl;
        if ( _M_rep < e.second ) {
            _M_val = e.first;
            _M_rep = e.second;
        }
    }
};

int
main(int argc, char *argv[])
{
    int a[] = {2,456,34,3456,2,435,2,456,2};
    std::map<int,int> m; 

    // load the map
    for(unsigned int i=0; i< sizeof(a)/sizeof(a[0]); i++) 
        m [a[i]]++;

    // find the max occurence...
    maxoccur ret = std::for_each(m.begin(), m.end(), maxoccur());
    std::cout << "value:" << ret._M_val << " max repetition:" << ret._M_rep <<  std::endl;

    return 0;
}

Answer 5

un poco de pseudocódigo:

//split string into array firts
strsplit(numbers) //PHP function name to split a string into it's components
i=0
while( i < count(array))
 {
   if(isset(list[array[i]]))
    {
      list[array[i]]['count'] = list + 1
    }
   else
    {
      list[i]['count'] = 1
      list[i]['number']
    }
   i=i+1
 }
usort(list) //usort is a php function that sorts an array by its value not its key, Im assuming that you have something in c++ that does this
print list[0]['number'] //Should contain the most used number

Answer 6

El algoritmo hash (conteo de compilaciones [i] = #occurrences (i) en tiempo básicamente lineal) es muy práctico, pero en teoría no es estrictamente O (n) porque podría haber colisiones hash durante el proceso.

Un caso especial interesante de esta pregunta es el algoritmo mayoritario, donde desea encontrar un elemento que esté presente en al menos n / 2 de las entradas de la matriz, si existe dicho elemento.

Aquí hay una explicación rápida , y una explicación más detallada de cómo hacer esto en tiempo lineal, sin ningún tipo de truco hash.

Answer 7

Si el rango de elementos es grande en comparación con el número de elementos, como otros han dicho, simplemente ordenaría y escanearía. Este es el tiempo n * log n y no hay espacio adicional (tal vez log n adicional).

El problema con el orden de conteo es que, si el rango de valores es grande, puede tomar más tiempo inicializar la matriz de conteo que ordenar.

Answer 8

Aquí está mi versión completa y probada, usando un std :: tr1 :: unordered_map .

Hago esto aproximadamente O (n). Primero itera a través de los n valores de entrada para insertar / actualizar los recuentos en el unordered_map , luego hace un partial_sort_copy que es O (n). 2 * O (n) ~ = O (n).

#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iostream>

namespace {
// Only used in most_frequent but can't be a local class because of the member template
struct second_greater {
    // Need to compare two (slightly) different types of pairs
    template <typename PairA, typename PairB>
    bool operator() (const PairA& a, const PairB& b) const
        { return a.second > b.second; }
};
}

template <typename Iter>
std::pair<typename std::iterator_traits<Iter>::value_type, unsigned int>
most_frequent(Iter begin, Iter end)
{
    typedef typename std::iterator_traits<Iter>::value_type value_type;
    typedef std::pair<value_type, unsigned int> result_type;

    std::tr1::unordered_map<value_type, unsigned int> counts;

    for(; begin != end; ++begin)
        // This is safe because new entries in the map are defined to be initialized to 0 for
        // built-in numeric types - no need to initialize them first
        ++ counts[*begin];

    // Only need the top one at this point (could easily expand to top-n)
    std::vector<result_type> top(1);

    std::partial_sort_copy(counts.begin(), counts.end(),
                           top.begin(), top.end(), second_greater());

    return top.front();
}

int main(int argc, char* argv[])
{
    int a[] = { 2, 456, 34, 3456, 2, 435, 2, 456, 2 };

    std::pair<int, unsigned int> m = most_frequent(a, a + (sizeof(a) / sizeof(a[0])));

    std::cout << "most common = " << m.first << " (" << m.second << " instances)" << std::endl;
    assert(m.first == 2);
    assert(m.second == 4);

    return 0;
}

Answer 9

Estará en O (n) ............ pero la cosa es el gran no. de matriz puede tomar otra matriz con el mismo tamaño ............

para (i = 0; i

mar = cuenta [o]; index = o;

para (i = 0; i

entonces la salida será ......... el elemento index se produce para max no. de veces en esta matriz ........

aquí a [] es la matriz de datos donde necesitamos buscar la ocurrencia máxima de cierto no. en una matriz .......

cuenta [] que tiene la cuenta de cada elemento .......... Nota: ya sabemos que el rango de datos estará en la matriz. decir por ejemplo. los datos en esa matriz varían de 1 a 100 ... luego tienen la matriz de conteo de 100 elementos para realizar un seguimiento, si ocurrió un incremento del valor indexado en uno ........