请用c++写一段代码解决问题:给定n个正整数,利用贪心法编写程序,找出它们中出现次数最多的数。如果这样的数有多个,请输出最小的一个。 输入说明: 输入第1行为一个正整数n,表示数字的个数 输入第2行为n个整数,相邻数之间用空格隔开 输入说明: 输出出现次数最多的数,如果有多个,则输出最小值 输入示例: 6 10 1 10 20 30 20 输出示例: 10
时间: 2024-02-24 13:58:09 浏览: 109
C++计算每个字符出现的次数
5星 · 资源好评率100%
好的,下面是用 C++ 编写的解决方案:
```cpp
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
map<int, int> cnt;
int max_cnt = 0, max_num = -1;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
if (++cnt[num] > max_cnt || (cnt[num] == max_cnt && num < max_num)) {
max_cnt = cnt[num];
max_num = num;
}
}
cout << max_num << endl;
return 0;
}
```
这个程序首先读入数字的个数 `n`,然后使用 `map` 来记录每个数字出现的次数。遍历输入的数字,对于每个数字,我们将它的计数器加 1,并判断当前数字出现次数是否大于之前记录的最大出现次数 `max_cnt`。如果是,或者次数相同但当前数字比之前记录的最大数字 `max_num` 更小,就更新 `max_cnt` 和 `max_num`。最后输出 `max_num` 即可。
这个算法的时间复杂度是 $O(n \log n)$,其中 $n$ 是数字的个数。`map` 的插入和查找操作的时间复杂度都是 $O(\log n)$,我们需要对每个数字进行一次插入或查找,因此总时间复杂度是 $O(n \log n)$。
阅读全文