häufigsten Wert C++ mit Karte

Question

finden Sie den häufigsten Wert (das mit der höchsten Frequenz). Wenn zwei (oder mehr) Werte die gleiche Frequenz einer von ihnen wählen, haben zufällig

muss ich mit dem Zufallsbit helfen

map<int, int > myp; 
    int con = 0; 
    for (int h = 0; h < distan.size(); h++) { 

     con = (int) count(distan.begin(), distan.end(), distan[h]); 
     myp.insert(pair<int, int> (con, distan[h])); 
    } 
    //getting the highest frequency value 
    int max = 0; 
    int temp_max = max; 

    max = max_element(myp.begin(), myp.end())->first; 
    cout<<con<<endl; 
    data_labels.push_back(myp[max]); 
    myp.clear(); 

Answer 1

Ich denke, hier zufällig bedeutet, dass Sie einen von ihnen wählen können, nicht unbedingt zufällig. Wie auch immer, mit dem aktuellen Algorithmus müssten Sie multimap verwenden, um die Zählungen zu speichern, da die map den alten Wert (das Element aus Ihrer Eingabe) ersetzt.

Darüber hinaus ist die obige Lösung nicht sehr effektiv. Es durchläuft im Grunde die Eingabe n mal (wobei n die Anzahl der Eingabeelemente ist) und verarbeitet für jeden Schritt alle Werte erneut, d. H. Die Komplexität ist quadratisch - O(n*n).

Die effiziente Art und Weise ist es, die map zu verwenden, um den aktuellen Zählerstand für jeden Schlüssel zu speichern (O(n*log2(n))) und am Ende wählen Sie die Taste mit Maximalwert (O(n)):

map<int, int> counts; 
for (int h = 0; h < distan.size(); h++) { 
    ++counts[distan[h]]; 
} 

int max = -1; 
int maxKey; 
// or vector<int> maxKeys; 
for (map<int, int>::const_iterator it = m.begin(); it != m.end(); ++it) { 
    if (it->second > max) { 
     maxKey = it->first; 
     max = it->second; 
     // or maxKeys.reset(); maxKeys.push(it->first); 
    } 
    else if (it->second == max) { 
     // you can maintain list of the inputs with max occurences here 
     maxKeys.push(it->first); 
    } 
} 
// in maxKey we have the key with max number of occurences 
// in max we have the max number of occurences 
// if max stays -1, maxKey will be invalid, i.e. input was empty 
// or in maxKeys you can have list and choose random one