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;
    
}