trouver plus occurence de l'élément dans le tableau

Ici est simple programme pour trouver l'élément qui revient le plus souvent dans un tableau:

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    int a[] = {1,2,3,4,4,4,5};
    int n = sizeof(a) / sizeof(int);
    int max = 0;
    int result = 0;
    int *b = new int[n];
    for (int i = 0;  i < n;  i++) {
        b[a[i]] = (b[a[i]] || 0) + 1;
        if (b[a[i]] > max) {
            max = b[a[i]];
            result = a[i];
        }
    }
    cout << result << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

Mais il ne fonctionne pas; il imprime 1. Pourquoi?

Pouvez-vous garantir que le tableau est toujours triée selon votre exemple? Ou pouvez-vous garantir que toutes les occurrences d'un élément donné sera consécutives? Si oui, plus simple, plus rapide des algorithmes en O(1) de stockage supplémentaire existent.

OriginalL'auteur user457463 | 2010-09-26

  1. 11

    Puisque vous êtes vecteur anway, pourquoi ne pas remplacer int *b=new int [n]; avec std::vector<int> b(n)? Cela prend également soin de libération de la mémoire, vous avez oublié de delete[] b.

    Mais comme d'autres l'ont mentionné, votre solution sera de se briser si le tableau contient des éléments plus grands que n. Une meilleure approche serait de compter les éléments d'une cartographie de type int. De cette façon, vous pouvez également compte des éléments qui ne peuvent pas être utilisé comme un index de tableau, par exemple des chaînes de caractères.

    Il n'y a également aucune raison de se limiter à des tableaux. Voici une solution générique qui fonctionne avec n'importe quel conteneur de moins comparable type d'élément:

    #include <algorithm>
#include <iterator>
#include <map>

struct by_second
{
    template <typename Pair>
    bool operator()(const Pair& a, const Pair& b)
    {
        return a.second < b.second;
    }
};


template <typename Fwd>
typename std::map<typename std::iterator_traits<Fwd>::value_type, int>::value_type
most_frequent_element(Fwd begin, Fwd end)
{
    std::map<typename std::iterator_traits<Fwd>::value_type, int> count;

    for (Fwd it = begin; it != end; ++it)
        ++count[*it];

    return *std::max_element(count.begin(), count.end(), by_second());
}

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> test {1, 2, 3, 4, 4, 4, 5};
    std::pair<int, int> x = most_frequent_element(test.begin(), test.end());
    std::cout << x.first << " occured " << x.second << " times";
}
    +1 pour éviter le manuel de gestion de la mémoire, si possible.
    Uhm, votre montage est probablement techniquement très bien, mais compte tenu de la question, je pense que ton code est trop compliqué. L'interlocuteur est encore à apprendre les bases, nous laissons pas submerger avec des modèles et des itérateur de détails pour l'instant...
    Oui, typename est nécessaire.
    le typename s'applique à value_type, de ne pas map_t. Si vous omettez le typename, puis map_t::value_type est considéré comme un non-type et puis le compilateur est accordée à rejeter by_second<map_t::value_type> au moment de l'analyse du modèle parce que by_second nécessite un type d'argument.
    Une tâche comme ça (bon, c'était de comptage de mot occurrences dans un texte) a été parmi les premiers à mes élèves jamais eu à faire. Bien sûr, à cette époque, ils ne pouvaient que utilisation modèles, mais qui était très bien. Manuellement de jongler avec la mémoire est bien pire que cela.

    OriginalL'auteur fredoverflow

  2. 6

    Vous n'avez pas initialisé votre tableau b. Vous pouvez le faire comme ceci:

    int *b=new int [n]();
                  ^^

    Une fois que c'est fait, vous pouvez incrémenter votre fréquence tableau:

    b[a[i]]++;

    en place de

    b[a[i]]=(b[a[i]]||0)+1;

    Votre façon de faire (b[a[i]]||0)+1 œuvres dans les langues, comme Javascript, Perl où non initialisé élément de tableau aura une valeur spéciale appelée undef ou null. C++ n'a pas quelque chose comme ça et un tableau non initialisé aura ordures.

    +1 pour la solution la plus simple. Bien que ce programme est encore fragile en ce qu'il va se planter si la matrice a a des valeurs comme {1, 600, 765, 2000, 600}

    OriginalL'auteur codaddict

  3. 1

    Vous devez initialiser votre tableau b à zéro.

     b[a[i]]||0

    ne fonctionnera pas, vous ne savez pas ce qui est en b à l'origine.

    Plus court code : 

    int main(int argc, char *argv[])
{
    int a[]={1,2,3,4,4,4,5};
    int n = sizeof(a)/sizeof(int );
    int *b=new int [n];
    fill_n(b,n,0); //Put n times 0 in b

    int val=0; //Value that is the most frequent
    for (int i=0;i<n;i++)
        if( ++b[a[i]] >= b[val])
            val = a[i];

    cout<<val<<endl;
    delete[] b;
    return 0;
}

    ATTENTION :
    votre code (le mien aussi) ne peut fonctionner que si la valeur maximale est plus faible que le nombre de valeurs dans le tableau un.

    Si ce n'est pas le cas et la valeur maximale est beaucoup plus grande que le nombre d'éléments, vous pouvez trier le tableau et ensuite, la recherche en temps linéaire (et de la constante de l'espace) pour la valeur maximale.

    OriginalL'auteur Loïc Février

  4. 0

    Ici, O(n), O(1) dans l'espace général de la solution qui fonctionne sur triés plages.

    #include <iostream>

template <class ForwardIterator>
ForwardIterator
most_common(ForwardIterator first, ForwardIterator last) {
  /** Find the most common element in the [first, last) range.

      O(n) in time; O(1) in space.

      [first, last) must be valid sorted range.
      Elements must be equality comparable.
  */
  ForwardIterator it(first), max_it(first);
  size_t count = 0, max_count = 0;
  for ( ; first != last; ++first) {
    if (*it == *first) 
      count++;
    else {
      it = first;
      count = 1;
    }      
    if (count > max_count) {
      max_count = count;
      max_it = it;
    }
  }  
  return max_it;
}    
int main() {
  int a[] = {1, 2, 3, 4, 4, 4, 5};
  const size_t len = sizeof(a) / sizeof(*a);
  std::cout << *most_common(a, a + len) << std::endl;
}

    OriginalL'auteur jfs

  5. 0

    application qui tire profit du fait que la carte est triée.

    #include <iostream>
#include <vector>
#include <map>

using namespace std;

template<class T> pair<T, int> getSecondMostOccurance(vector<T> & v) {
    map<T, int> m;

    for ( int i = 0; i < v.size(); ++i ) {
        m[ v[i] ]++;
    }
    return *m.end();
}

int main() {
    int arr[] = {1, 4, 5, 4, 5, 4};
    pair<int, int> p = getSecondMostOccurance(vector<int>(arr, arr+7));
    cout << "element: " << p.first << " count: " << p.second << endl;
    return 0;
}

    OriginalL'auteur user167698