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

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 apparaît 4 fois. C’est le nombre maximum de fois que 2 se produit.

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.

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:

Itérer sur tous les éléments, en gardant une trace des comptes séparés. Cet algorithme sera toujours O (n).

Si vous avez la RAM et que vos valeurs ne sont pas trop grandes, utilisez le sorting par comptage .

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

 #include  #include  #include  // functor struct maxoccur { int _M_val; int _M_rep; maxoccur() : _M_val(0), _M_rep(0) {} void operator()(const std::pair &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 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; }

un peu de pseudo-code:

 //split ssortingng into array firts strsplit(numbers) //PHP function name to split a ssortingng 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

L’algorithme de hachage (nombre de constructions [i] = # occurrences (i) dans un temps fondamentalement linéaire) est très pratique, mais n’est théoriquement pas ssortingctement O (n) car il pourrait y avoir des collisions de hachage pendant le processus.

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

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

Si la gamme d’éléments est grande comparée au nombre d’éléments, je voudrais, comme d’autres l’ont déjà dit, simplement sortinger et parsingr. C’est le temps n * log n et pas d’espace supplémentaire (peut-être log n supplémentaire).

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

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

Je fais ceci approximativement O (n). Tout d’abord, il effectue une itération à travers les n valeurs d’entrée pour insérer / mettre à jour les comptages dans le unordered_map , puis effectue une partial_sort_copy qui est O (n). 2 * O (n) ~ = O (n).

 #include  #include  #include  #include  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  bool operator() (const PairA& a, const PairB& b) const { return a.second > b.second; } }; } template  std::pair::value_type, unsigned int> most_frequent(Iter begin, Iter end) { typedef typename std::iterator_traits::value_type value_type; typedef std::pair result_type; std::tr1::unordered_map counts; for(; begin != end; ++begin) // This is safe because new ensortinges 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 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 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; }

Ce sera dans O (n) ………… mais la chose est le grand non. du tableau peut prendre un autre tableau avec la même taille …………

pour (i = 0; i

mar = compte [o]; indice = o;

pour (i = 0; i

alors la sortie sera ……… l’ index d’ élément est apparu pour max no. de fois dans ce tableau ……..

ici un [] est le tableau de données où nous devons rechercher l’occurrence maximale de certains non. dans un tableau …….

count [] ayant le compte de chaque élément ………. Remarque: nous soaps déjà que la plage de données sera dans array .. disons 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émente la valeur indexée d’un …….