如何从向量或数组中选择最常见的数字？（TOP5 排行榜）C++

Question

我有一个整数向量。我想选择最常见的数字。我想列出前 5 名。例如：

std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};

最常见的数字是：TOP 1：32，TOP 2：11，TOP 3：12，TOP 4：9；

选择它们后，我想将其存储到另一个向量中：最常见的数字。

Answer 1

这是另一种算法， any 的成本将是 O(n) k，加上一个不错的缓存位置。

1.首先将所有元素存储在一个unordered_mapO(N) 中

std::unordered_map<int, int> m;
for(const auto ele: numbers) {
  m[ele]++;   
}

2. 转储 O(N) 对向量中的所有元素

std::vector<std::pair<int, int>> temp;  
for(const auto& ele: m) {
 temp.emplace_back(ele.first ,  ele.second);   
}

3.现在使用 nth_element 找到第 k 个秩 O(N)

std::nth_element( temp.begin(), temp.begin()+k ,
temp.end(), [](const auto& p1, const auto& p2) {
        // Strict weak ordering
        if (p1.second > p2.second) {
            return true;
        }  if (p1.second < p2.second) {  
            return false;
        }
        return p1.first > p2.first; // We have to print large element first
    } );

4.显示输出

std::for_each( temp.begin(), temp.begin() +k - 1, [](const auto & p) {
    std::cout << p.first << " ";
});

Demo Here