c++ - 如何从 vector 或数组中选择最常见的数字？(TOP5 toplist) C++

Question

我有一个带有整数的 vector 。我想选择最常见的数字。我想列出一个前 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；

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

Answer 1

这是另一种算法，对于任何k，成本都是 O(n)，再加上合适的缓存局部性。

1.首先将所有元素存储在unordered_map O(N)

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

2.转储成对 vector 中的所有元素 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