J'ai quelques nombres stockés dans un vecteur. Je veux trouver quel nombre apparaît le plus dans le vecteur.Trouver les nombres qui apparaissent le plus dans un vecteur
Y at-il un algorithme simple/rapide (STL ou autre) qui fait cela?
Triez-le, puis parcourez-le et conservez un compteur que vous incrémentez lorsque le nombre actuel est le même que le nombre précédent et remettez-le à 0 sinon. Gardez également une trace de ce qui était la valeur la plus élevée du compteur jusqu'à présent et quel était le nombre actuel lorsque cette valeur a été atteinte. Cette solution est O(n log n) (à cause du tri). Vous pouvez également utiliser un hashmap de int à int (ou si vous savez que les nombres sont dans une plage limitée, vous pouvez simplement utiliser un tableau) et itérez sur le vecteur, en augmentant the_hashmap[current_number] de 1 pour chaque nombre. Ensuite parcourez la hashmap pour trouver sa plus grande valeur (et la clé qui lui appartient). Cela nécessite une structure de données hashmap (à moins que vous ne puissiez utiliser des tableaux qui seront également plus rapides), ce qui ne fait pas partie de STL.
Juste pour ajouter l'évidence, pour trier en utilisant le tri de STL: http://www.cplusplus.com/reference/algorithm/sort/ –
@ Steve314: unordered_map sera dans le prochain la norme. Ce n'est pas dans la norme 2003 (c'est-à-dire actuelle). – sepp2k
Wierd - J'ai en quelque sorte eu l'idée que TR1 était la "première révision de texte" de 2003. – Steve314
Voici comment je l'ai fait:
int max=0,mostvalue=a[0];
for(i=0;i<a.size();i++)
{
co = (int)count(a.begin(), a.end(), a[i]);
if(co > max)
{ max = co;
mostvalue = a[i];
}
}
Je ne sais pas comment il est rapide, à savoir O()? Si quelqu'un pouvait le calculer et l'afficher ici, ce serait bien.
C'est O (n * n), ce n'est donc pas la méthode la plus efficace mais elle est en lecture seule et ne nécessite aucun stockage supplémentaire si c'est important. –
O (n^2), car chaque fois que vous appelez count, il regarde chaque élément du vecteur. Cela peut être fait en O (n) (http://stackoverflow.com/questions/512590/computing-the-statistical-mode/512601#512601) –
Si vous voulez éviter le tri de votre vecteur v, utilisez une carte:
int max = 0;
int most_common = -1;
map<int,int> m;
for (vi = v.begin(); vi != v.end(); vi++) {
m[*vi]++;
if (m[*vi] > max) {
max = m[*vi];
most_common = *vi;
}
}
Cela nécessite plus de mémoire et a une durée d'exécution prévue très similaire. La mémoire requise doit être de l'ordre d'une copie vectorielle complète, moins s'il y a beaucoup d'entrées en double.
Voir les questions comme: http://stackoverflow.com/questions/1204313/counting-occurences-in-a-vector, http://stackoverflow.com/questions/2184336/how-to-get-the-most -represented-object-from-an-array – outis