Trovare la frequenza dei numeri in un determinato gruppo di numeri

Question

Supponiamo di avere un vettore / array in C ++ e desideriamo contare quale di questi N elementi ha le ricorrenze massime ripetitive e produrre il conteggio più alto. Quale algoritmo è più adatto per questo lavoro.

Esempio:

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

l'uscita è 4 perché 2 si verifica 4 volte. Questo è il numero massimo di volte in cui si verifica 2.

Answer 1

Ordina l'array e fai un passaggio rapido per contare ogni numero. L'algoritmo ha complessità O (N * logN).

In alternativa, crea una tabella hash, usando il numero come chiave. Memorizza nella tabella hash un contatore per ogni elemento che hai digitato. Sarai in grado di contare tutti gli elementi in un passaggio; tuttavia, la complessità dell'algoritmo ora dipende dalla complessità della tua funzione hasing.

Answer 2

Ottimizzato per lo spazio:

Quicksort (ad esempio) quindi scorre gli oggetti, tenendo traccia solo del conteggio maggiore. Nella migliore delle ipotesi O (N log N).

Ottimizzato per la velocità:

Scorrere su tutti gli elementi, tenendo traccia dei conteggi separati. Questo algoritmo sarà sempre O (n).

Answer 3

Se hai la RAM e i tuoi valori non sono troppo grandi, usa conteggio ordinamento .

Answer 4

Una possibile implementazione C ++ che utilizza STL potrebbe essere:

#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 po 'di pseudo-codice:

//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

L'algoritmo hash (build count [i] = #occurrences (i) in un tempo sostanzialmente lineare) è molto pratico, ma teoricamente non è strettamente O (n) perché potrebbero esserci collisioni hash durante il processo.

Un caso speciale interessante di questa domanda è l'algoritmo di maggioranza, in cui si desidera trovare un elemento che è presente in almeno n / 2 delle voci dell'array, se tale elemento esiste.

Ecco una spiegazione rapida , e una spiegazione più dettagliata di come farlo in tempo lineare, senza alcun tipo di inganno.

Answer 7

Se l'intervallo di elementi è ampio rispetto al numero di elementi, come altri hanno già detto, ordinerei e scansionerei. Questo è il tempo n * log n e nessuno spazio aggiuntivo (forse log n aggiuntivo).

Il problema con l'ordinamento di conteggio è che, se l'intervallo di valori è grande, può richiedere più tempo per inizializzare l'array di conteggio che per l'ordinamento.

Answer 8

Ecco la mia versione completa, testata, usando un std :: tr1 :: unordered_map .

Faccio questo approssimativamente O (n). Prima scorre attraverso gli n valori di input per inserire / aggiornare i conteggi in unordered_map , quindi esegue un partial_sort_copy che è 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

Sarà in O (n) ............ ma la cosa è il grande no. di array può accettare un altro array con le stesse dimensioni ............

for (i = 0; i

mar = conteggio [o]; index = o;

for (i = 0; i

l'output sarà ......... l'elemento indice si è verificato per max no. di volte in questo array ........

qui a [] è l'array di dati in cui è necessario cercare la massima occorrenza di certo no. in un array .......

count [] con il conteggio di ciascun elemento .......... Nota: abbiamo già saputo che la gamma di dati sarà in array. dire per es. i dati in quell'array vanno da 1 a 100 ....... quindi hanno l'array di conteggio di 100 elementi da tenere traccia, se si verifica aumenta il valore indicizzato di uno ........