练60.2 众数

解题思路

值域只有0～1000，用频次数组统计。按值从小到大扫描，只有频次严格更大才更新答案，自动保留最小众数。

正确性说明

按顺序完成所述运算后，每个输入元素都被处理在相应位置或统计项中。保存的中间状态与已处理数据对应，最终输出与题目定义一致。

易错点

同频时不更新到更大的值。

复杂度

时间O(n+1001)，空间O(1001)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int cnt[1001] = {};
    while (n--) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    int ans = 0;
    for (int i = 1; i <= 1000; i++)
        if (cnt[i] > cnt[ans])
            ans = i;
    cout << ans << "\n";
    return 0;
}