FDU 2018 | 1. 求众数

本文主要是介绍FDU 2018 | 1. 求众数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述

AcWing 3685 求众数

给定一个长度为 n 的整数序列，请你求出该序列的众数。

众数就是一个序列中出现次数最多的数字。

如果不唯一，则输出小的那个值。

输入格式

第一行输入一个整数 n，表示有 n 个数。
第二行输入 n个整数。

输出格式

输出序列中的众数，如果不唯一，则输出小的那个值。

数据范围
$1\le n\le 10^5$, 序列中整数的取值范围 $[-10^9,10^9]$ 。

输入样例

8
10 3 8 8 3 2 2 2

输出样例

2

2. 我的尝试

数据范围 $10^5$， $O(nlogn)$的算法即可满足，可以先把所有的数读入数组，再对数组排序，然后从头扫描数组找到排序后连续出现最多的数即为众数。

因为题目要求不唯一时输出最小的众数，因此扫描时的更新条件为if (cnt > max)

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;
int a[N];int main() {int n;cin >> n;for (int i = 0; i < n; i++)scanf("%d", &a[i]);sort(a, a + n);int cur = a[0], cnt = 0, res = a[0], max = -1;for (int i = 0; i <= n; i++){if (i < n && a[i] == cur) cnt ++;else {if (cnt > max){res = cur;max = cnt;}cur = a[i];cnt = 1;}}cout << res;}

这篇关于FDU 2018 | 1. 求众数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---