[NOIP 2006 普及组] 明明的随机数

题意

给出 N 个 1..1000 的随机整数。去掉重复数字后，按从小到大输出。

思路

Python 中 set(numbers) 可以去重，但集合本身没有固定顺序。再用 sorted(...) 排序：

python

1unique_numbers = sorted(set(numbers))

然后输出不同数字个数和排序后的列表即可。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：set 适合判重和去重。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：sorted() 返回一个新的有序列表。
print(*unique_numbers) 按空格展开输出列表。

代码

python

1
2
3
4
5
6n = int(input())
numbers = list(map(int, input().split()))
unique_numbers = sorted(set(numbers))

print(len(unique_numbers))
print(*unique_numbers)

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

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-08-14 15:18
 * update_at: 2026-08-14 15:18
 */
/* P1059 明明的随机数：布尔数组当桶用，相同的随机数只保留一个，再从小到大输出。 */

#include <iostream>

int main() {
    const int max_value = 1000;
    bool seen[max_value + 1];  // seen[x] = true 表示随机数 x 已经出现过
    for (int i = 1; i <= max_value; i += 1) {
        seen[i] = false;
    }

    int n;
    std::cin >> n;
    for (int i = 0; i < n; i += 1) {
        int x;
        std::cin >> x;
        seen[x] = true;  // 重复出现的数字只算一个
    }

    // 第一行输出不同数字的个数
    int count = 0;
    for (int i = 1; i <= max_value; i += 1) {
        if (seen[i]) {
            count += 1;
        }
    }
    std::cout << count << '\n';

    // 第二行按从小到大输出这些不同的数字
    bool first = true;
    for (int i = 1; i <= max_value; i += 1) {
        if (seen[i]) {
            if (!first) {
                std::cout << ' ';
            }
            std::cout << i;
            first = false;
        }
    }
    std::cout << '\n';

    return 0;
}

Pythonic 写法

set 去重 sorted：

python

1
2
3
4input()
nums = sorted(set(map(int, input().split())))
print(len(nums))
print(*nums)

STL 写法

C++ 里这道题是 sort + unique + erase 三行组合的标准场景：先把数装进 vector，sort 排序让相等的值相邻，unique 合并相邻重复并返回新的逻辑末尾，erase 再把尾段真正删掉，容器的 size() 才等于去重后的个数。和上面 main.cpp 用桶标记值域的做法相比，这里不依赖 1…1000 的值域，任何能比较大小的数据都适用。

对应的 cppbook 章节：unique：相邻去重与真正删除

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/**
 * 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-10-06 23:38
 * update_at: 2026-10-06 23:55
 */
// 这是 STL 写法：用 vector 存下所有随机数，靠 sort + unique + erase 三行完成去重与排序。

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

typedef long long ll;

ll n;
vector<int> a; // 随机数序列；值域只有 1..1000，元素用 int 足够

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }

    // 书上三行组合：sort 让相等的值相邻，unique 合并相邻重复并返回新的逻辑末尾，
    // erase 把逻辑末尾之后的尾段真正删掉，容器 size 才变小。
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    ll m = a.size(); // 去重后的个数
    cout << m << '\n';
    for (ll i = 0; i < m; i++) {
        if (i) {
            cout << ' ';
        }
        cout << a[i];
    }
    cout << '\n';

    return 0;
}

复杂度

设输入数量为 N，去重和排序总复杂度为 $O(N\log N)$ ，空间复杂度为 $O(N)$ 。

总结

去重后排序是 Python 的常见组合：sorted(set(a))。注意集合去重后要排序，不能直接输出集合。