Encontrar Frequência de números em um determinado grupo de números

Question

Suponhamos que temos um vector / matriz em C ++ e desejamos contar que estes elementos N tem ocorrências repetitivas máximos e de saída mais alta contagem. Qual algoritmo é o mais adequado para este trabalho.

exemplo:

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

a saída é 4 porque 2 ocorre 4 vezes. Esse é o número máximo de vezes 2 ocorre.

Answer 1

Classificar a matriz e, em seguida, fazer um passe rápido para contar cada número. O algoritmo tem complexidade O (N log N *).

Alternativamente, criar uma tabela hash, usando o número como a chave. Loja no contador de uma tabela hash para cada elemento que você digitou. Você vai ser capaz de contar todos os elementos em uma passagem; No entanto, a complexidade do algoritmo agora depende da complexidade de sua função hasing.

Answer 2

Optimizado para o espaço:

Quicksort (por exemplo), em seguida, iterar sobre os itens, mantendo o controle de apenas maior contagem. Na melhor das hipóteses O (N log N).

Optimizado para velocidade:

iterar sobre todos os elementos, mantendo o controle das contagens separadas. Este algoritmo será sempre O (n).

Answer 3

Se você tiver a RAM e os seus valores não são muito grandes, use contando tipo .

Answer 4

A possível implementação C ++ que faz uso de STL poderia 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

um pouco de pseudo-có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

O algoritmo de hash (contagem de construção [i] = #occurrences (I) em vez basicamente linear) é muito prático, mas é, teoricamente, não estritamente O (n) porque pode haver colisões de hash durante o processo.

Um caso especial interessante desta questão é o algoritmo maioria, onde você quiser encontrar um elemento que está presente em pelo menos n / 2 das entradas de matriz, se tal elemento existe.

Aqui é um explicação rápida , e uma explicação mais detalhada de como fazer isso em tempo linear, sem qualquer tipo de trickiness hash.

Answer 7

Se o intervalo de elementos é grande em comparação com o número de elementos, eu o faria, como já foi dito, apenas uma espécie e digitalização. Este é o tempo n * log n e nenhum espaço adicional (talvez log n adicional).

O problema com o tipo de contagem é que, se o intervalo de valores é grande, pode demorar mais tempo para inicializar a matriz de contagem do que a sorte.

Answer 8

Aqui está a minha completa, testada, versão, usando um std::tr1::unordered_map.

Eu faço isso O (n), aproximadamente. Em primeiro lugar, itera através dos valores de entrada n para inserir / actualizar as contagens no unordered_map, em seguida, ele faz uma partial_sort_copy que é 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

Ele wil ser em O (n) ............ mas a coisa é grande não. de matriz pode ter um outro array com mesmo tamanho ............

for (i = 0; i

mar = contar [o]; índice S =;

for (i = 0; i

, então a saída será ......... o elemento índice é ocorreu para max nenhuma. de vezes nessa matriz ........

aqui a [] é a matriz de dados onde precisamos procurar a ocorrência máximo de certo não. em uma matriz .......

contar [] ter a contagem de cada elemento .......... Nota: nós alrdy KNW a gama de datas será em ordem .. dizer, por exemplo. as datas em que os intervalos de matriz de 1 a 100, em seguida, ....... tem a matriz de contagem de 100 elementos para manter o controle, se a sua ocorreu increament o valor indexado por um ........