首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >如何从向量或数组中选择最常见的数字?(TOP5 toplist) C++

如何从向量或数组中选择最常见的数字?(TOP5 toplist) C++
EN

Stack Overflow用户
提问于 2020-01-30 11:45:11
回答 4查看 337关注 0票数 3

我有一个带整数的向量。我想选择最常见的数字。我想列个前五名的名单。例如:

代码语言:javascript
运行
复制
std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};

最常见的数字是:前1: 32,前2: 11,前3: 12,前4: 9;

在我选择了它们之后,我想将它存储到另一个向量中:最常见的数字。

EN

回答 4

Stack Overflow用户

发布于 2020-01-30 12:05:05

您可以创建一个unordered_map<int,int> mp,在这里可以存储每个数字的计数,比如mp[32] = 3

接下来,您需要找到前五位元素

  1. Time复杂性: O(mlogm):您可以按降序排序映射(要对其排序,必须使用额外的向量),并取前5 elements.
  2. Time复杂性: O(m):或者您可以在整个映射上迭代5次以获得顶级文件元素。每次迭代时,都会找到我们的topFive向量中还没有出现的最高频率的数字。

M:地图上的条目数。

票数 3
EN

Stack Overflow用户

发布于 2020-01-30 12:09:48

我已经做了这个例子,并发表了评论。它至少需要C++11。

代码语言:javascript
运行
复制
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>

int main(void) {
  std::map<int, int> ans;
  std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};
  std::vector<std::pair<int, int>> sorted;
  std::vector<int> common;
  // Step 1 Accumulate into a map, counting occurrences
  for (auto number : numbers) {
    ans[number]++;
  }
  // Step 2 Make a linear list, putting the count first then the value
  for (auto& ent : ans) {
    sorted.emplace_back(ent.second, ent.first);
  }
  // Step 3 sort it, by count ascending
  std::sort(std::begin(sorted), std::end(sorted));

  // Step 4 Get commonest 5 (or fewer)
  for (int i = 1; i<= 5; ++i) {
    int index = sorted.size() - i;
    if (index >= 0) {
      common.push_back(sorted[index].second);
    }
  }

  // Step 5 print out
  for (auto i : common) {
    std::cout << i << std::endl;
  }
  return 0;
}
票数 2
EN

Stack Overflow用户

发布于 2020-01-30 12:18:11

您可以这样做:创建一个集合,这样就可以摆脱重复,然后在向量中找到集合中每一项的频率,这样就可以创建一对(类似int、int),将其推入向量中,最后使用您自己的谓词对其排序:

现在,对于顶部的x,您可以做一个for循环,或者只是调整向量的大小,如果您确定这会带来什么后果的话。

代码语言:javascript
运行
复制
std::vector<int> numbers{32, 32, 32, 12, 12, 11, 11, 11, 9};
std::set<int> mySet(numbers.begin(), numbers.end());
std::vector<std::pair<int, int>> result{};

for(const auto& x : mySet)
{
    result.push_back(std::make_pair(x , std::count(numbers.begin(), numbers.end(), x)));
}
std::sort(result.begin(), result.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b){return (b.second < a.second);});
//result.resize(3);
std::cout << "Top: " << std::endl;
for(const auto& x : result)
{
   std::cout << x.first << ':' << x.second << std::endl;
}

其结果将是:

排名: 11:3 32:3 12:2 9:1

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/59985335

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档