Valeurs les plus courantes dans un tableau

Question

Comment rechercher les trois éléments les plus courants d'un tableau? Je travaille avec un tableau de longueur 10 000 avec des éléments = entier aléatoire de 0 à 100.

Je pensais utiliser deux tableaux, un de longueur 100 et juste en incrémentant en utilisant une instruction if. Cependant, je me demandais s'il existait un moyen pour qu'une seule boucle for/if (déclaration) puisse être utilisée pour trouver ces valeurs.

Answer 1

Si vous faites cela en un nombre constant de passages dans la liste, vous avez besoin d'une seconde structure de données.

Si vous avez des limites inférieures et supérieures pour les valeurs de cet ensemble et que les valeurs sont relativement denses, alors un tableau de compteurs est une bonne solution.

Sinon, il est préférable d'utiliser un Map<Integer, Integer>, où les clés sont des éléments de l'ensemble et les valeurs sont des compteurs.

Analyse

Si vous ne savez pas avoir des bornes inférieures/supérieures sur l'ensemble avant de commencer, vous n'avez pas grand un tableau des compteurs à allouer. Donc, vous devez faire un passage préliminaire sur le tableau pour trouver les limites ... et vous avez maintenant une solution à deux passes. Si vous avez des limites inférieures et supérieures mais que l'ensemble est clairsemé, le coût d'initialisation de la matrice de comptes + le coût de la recherche des trois plus grands comptes dominera le coût du comptage des éléments de l'ensemble. Si la différence est suffisamment grande (c'est-à-dire que l'entrée est grande & très éparse), une HashMap sera plus rapide et prendra moins de mémoire.

Vous pouvez également

Si vous êtes autorisé à modifier le tableau, vous pouvez trier dans l'ordre ascendant O(NlogN) puis trouver les trois éléments les plus communs en un seul passage sur le tableau trié.

Answer 2

Vous pouvez le faire en une seule fois, mais je pense que vous avez toujours besoin de ce second tableau.

I.e. boucle sur votre tableau d'entrée, et chaque fois que vous voyez une valeur, vous incrémentez l'index approprié dans votre tableau 'counter'. Mais, gardez aussi 3 index 'top' (triés). Chaque fois que vous incrémentez, vérifiez votre nouvelle valeur par rapport à la valeur dans les 3 premiers index, en tenant compte du fait que vous pourriez avoir à réorganiser simplement votre liste de valeurs «supérieures».

Answer 3

Il existe probablement de meilleurs moyens de le faire, mais c'est un moyen. Je viens d'imprimer le tableau des modes, mais vous pouvez le trier pour voir quel est le nombre qui s'est le plus produit. C'est simple parce que nous connaissons les limites supérieures et inférieures des nombres avec lesquels nous jouons, mais si vous ne connaissez pas ces limites, alors vous devez suivre le conseil donné par Stephen C.

public class Main { 

    public static void main(String[] args) { 

     int i; 
     int value; 
     //one greater than max value because Math.random always returns a value less than 1.0 
     //this number also works good for our mode array size 
     int maxValue = 101; 
     int[] originalArray = new int[10000]; 
     int[] modeArray = new int[maxValue]; 

     for(i = 0; i < originalArray.length; i++){ 
      value = (int) (Math.random() * maxValue); 
      originalArray[i] = value; 
     } 


     for(i = 0; i < originalArray.length; i++){ 
      modeArray[originalArray[i]] += 1; 
     } 

     for(i = 0; i < modeArray.length; i++){ 
      System.out.println("Number " + i + " occurred " + modeArray[i] + " times"); 
     } 

    } 

} 

Answer 4

//find majority of a value in a array — O(n log n) -> wrost case O(n) 
void findMajority(){ 
    //sort 
    sort(begin(sarray),end(sarray)); 
    //sarray[0] is our first number already counted 
    int cont=1; 
    int leader = sarray[0]; 
    //temp variables to know when we changed to a different number 
    int tempLeader=0; 
    int tempCont=0; 
    //loop through sarray.size() 
    for(unsigned int i=1; i<size; i++){ 
     if(tempLeader!=sarray[i]) //if we changed number tempCont is 0 
      tempCont=0; 

     if(sarray[i]==leader){ //if the current number in the array is our leader then keep counting 
      cont++; 
     } 
     else{ //if not, then our new number will be tempLeader and we count that one 
      tempLeader=sarray[i]; 
      tempCont++; 
      if(tempCont>cont){ //its not higher occurences than our last number? skip, else we got a new leader 
       leader=tempLeader; 
       cont=tempCont; 
       tempLeader=0; 
       tempCont=0; 
      } 
     } 
    } 
    cout << "leader is" << leader << endl; 
} 

désolé, sa solution merdique, mais il fonctionne comme vous avez demandé, espère que cela aide