数字排序

形式化题目

给定 $n$ 个整数，输出每个出现过的整数及其出现次数。输出顺序按出现次数从多到少排列；次数相同时按数值从小到大排列。

思路

先看一个不借助计数数组的小数据基准：先收集互不相同的数字，再按“次数最多、值最小”的规则反复选出下一个要输出的数字。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:51
 */
// brute.cpp：小数据基准，枚举不同数字并反复选择当前应输出的数字。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];

    vector<int> values;
    for (int i = 0; i < n; i++) {
        bool exists = false;
        for (int j = 0; j < (int)values.size(); j++) {
            if (values[j] == numbers[i]) exists = true;
        }
        if (!exists) values.push_back(numbers[i]);
    }

    vector<int> count(values.size(), 0);
    for (int i = 0; i < (int)values.size(); i++) {
        for (int j = 0; j < n; j++) {
            if (numbers[j] == values[i]) count[i]++;
        }
    }

    vector<int> used(values.size(), 0);
    for (int round = 0; round < (int)values.size(); round++) {
        int best = -1;
        for (int i = 0; i < (int)values.size(); i++) {
            if (used[i]) continue;
            if (best == -1 || count[i] > count[best] ||
                (count[i] == count[best] && values[i] < values[best])) {
                best = i;
            }
        }
        used[best] = 1;
        cout << values[best] << ' ' << count[best] << '\n';
    }

    return 0;
}

brute.cpp 用两重循环统计频率，再每次扫描选出当前最优条目，逻辑最贴合题意，适合作为对拍基准。

正式做法分两步：

统计：给出的数都是 $0 \sim 1000$ 的非负整数，直接用大小为 $1001$ 的计数数组 count_value 记录每个数字的出现次数。
排序：把所有出现过的数字封装成 (value, count) 条目，按比较器排序——先让较大的 count 在前，count 相同时让较小的 value 在前。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:51
 */
#include <bits/stdc++.h>
using namespace std;

int count_value[1005]; // count_value[x] 表示数字 x 出现的次数

struct Item {
    int value; // 数字本身
    int count; // 出现次数
};

// 排序规则：次数大的在前，次数相同时数值小的在前。
bool compare_item(const Item &left, const Item &right) {
    if (left.count != right.count) return left.count > right.count;
    return left.value < right.value;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        count_value[value]++;
    }

    vector<Item> items;
    for (int value = 0; value <= 1000; value++) {
        if (count_value[value] > 0) {
            Item current = {value, count_value[value]};
            items.push_back(current);
        }
    }
    sort(items.begin(), items.end(), compare_item);

    for (int i = 0; i < (int)items.size(); i++) {
        cout << items[i].value << ' ' << items[i].count << '\n';
    }

    return 0;
}

复杂度

时间：统计为 $O(n)$ ，设不同数字数为 $k$ ，排序为 $O(k\log k)$ 。
空间： $O(1001 + k)$ 。

总结

有重复元素的排序题，先压缩为“值和频次”的条目，再把题意的主关键字（次数降序）和次关键字（数值升序）完整写进比较器即可。计数数组比 map 更快，适合值域小的题目。

目录

形式化题目

思路

代码

复杂度

总结