最常見的值C++使用map

Question

找到最常見的值（頻率最高）。如果兩個（或更多）的值具有相同的頻率選擇其中一個隨機

我需要用隨機位

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

我想隨機這裏意味着你可以選擇其中的任何幫助，不一定是隨機的。無論如何，使用當前算法，您需要使用multimap來存儲相同數字的計數，map將替換舊值（來自輸入的元素）。

此外，上述解決方案不是非常有效。它基本上遍歷輸入n次（其中n是輸入元素的數量），並且對於每一步它再次處理所有的值，即複雜度是二次的 - O(n*n)。

的有效方法是使用map來存儲每個鍵（O(n*log2(n))）當前計數並在年底選擇具有最大值的關鍵（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