Trouver la fréquence des nombres dans un groupe de nombres donné

Question

Supposons que nous avons un vecteur / tableau en C ++ et que nous souhaitons compter lequel de ces N éléments a le plus grand nombre d'occurrences répétitives et générer le nombre le plus élevé. Quel algorithme convient le mieux à ce travail.

exemple:

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

la sortie est 4 car 2 se produit 4 fois. C’est le nombre maximum de fois que 2 se produit.

Answer 1

Triez le tableau, puis effectuez une passe rapide pour compter chaque nombre. L’algorithme a une complexité O (N * logN).

Vous pouvez également créer une table de hachage en utilisant le nombre comme clé. Stockez dans la table de hachage un compteur pour chaque élément saisi. Vous pourrez compter tous les éléments en un seul passage. Cependant, la complexité de l'algorithme dépend maintenant de la complexité de votre fonction hasing.

Answer 2

Optimisé pour l'espace:

Quicksort (par exemple) puis parcourez les éléments en conservant uniquement le compte le plus important. Au mieux, O (N log N).

Optimisé pour la vitesse:

Parcourez tous les éléments en gardant une trace des décomptes séparés. Cet algorithme sera toujours O (n).

Answer 3

Si vous disposez de la RAM et que vos valeurs ne sont pas trop grandes, utilisez le tri par comptage .

Answer 4

Une implémentation C ++ possible utilisant STL pourrait être:

#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 peu de pseudo-code:

//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’algorithme de hachage (build count [i] = #occurrences (i) en temps essentiellement linéaire) est très pratique, mais n’est théoriquement pas strictement O (n) car il pourrait y avoir des collisions de hachage au cours du processus.

Un cas particulier intéressant de cette question est l’algorithme majoritaire, dans lequel vous souhaitez trouver un élément présent dans au moins n / 2 des entrées du tableau, s’il en existe.

Voici une explication rapide , et une explication plus détaillée de la procédure à suivre pour y parvenir. temps linéaire, sans aucune astuce de hachage.

Answer 7

Si le nombre d'éléments est grand par rapport au nombre d'éléments, comme d'autres l'ont déjà dit, il suffit de trier et d'analyser. C’est le temps n * log n et pas d’espace supplémentaire (peut-être le log n supplémentaire).

Le problème du tri par comptage est que, si la plage de valeurs est grande, l’initialisation du tableau de comptage peut prendre plus de temps que son tri.

Answer 8

Voici ma version complète, testée, utilisant un std :: tr1 :: unordered_map .

Je fais ceci approximativement O (n). Tout d'abord, il itère via les n valeurs d'entrée pour insérer / mettre à jour les comptes dans le unordered_map , puis il effectue une partial_sort_copy qui est 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

Ce sera dans O (n) ............ mais le truc c'est le grand non. d'un tableau peut prendre un autre tableau de même taille ............

pour (i = 0; i

mar = compte [o]; index = o;

pour (i = 0; i

alors le résultat sera ......... l'élément index est apparu pour max non. de fois dans ce tableau ........

ici un [] est le tableau de données dans lequel nous devons rechercher l'occurrence maximale de certains non. dans un tableau .......

count [] ayant le compte de chaque élément .......... Remarque: nous savons déjà que la plage de données sera dans le tableau. dire par exemple. les données dans ce tableau vont de 1 à 100 ....... puis ont le tableau de comptage de 100 éléments à garder en trace, si cela se produit incrément la valeur indexée d'un .......