明明的随机数

题目描述

明明生成了 $N$ （ $N \leq 100$ ）个 $1$ 到 $1000$ 之间的随机整数，重复的数字只保留一个，再把这些数从小到大排序，请完成「去重」与「排序」。输入第 1 行为正整数 $N$ ，第 2 行为 $N$ 个用空格隔开的正整数；输出第 1 行为不相同的随机数个数 $M$ ，第 2 行为从小到大排好序的 $M$ 个正整数。

text

1
2输入: 10 / 20 40 32 67 40 20 89 300 400 15
输出: 8 / 15 20 32 40 67 89 300 400

思路

值域只有 $[1,1000]$ ，读到数字 $v$ 就执行 bucket[v] = 1，重复写同一格即完成去重；输出时按下标 $1$ 到 $1000$ 扫描，下标递增方向就是数值递增方向，天然有序。总时间 $O(N+V)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-29 22:38
# update_at: 2026-09-29 22:38

import sys

MAX_VALUE = 1000  # 题面保证每个随机数都在 [1, 1000]，桶的下标就是随机数本身


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                                  # 随机数个数，只决定读多少 token
    bucket = bytearray(MAX_VALUE + 1)               # 桶：bucket[v] = 1 表示数字 v 出现过
    for _ in range(n):                              # 顺序消费接下来的 n 个随机数
        bucket[next(data)] = 1                      # 重复的数字写进同一个格子，去重自动完成
    unique = [v for v in range(1, MAX_VALUE + 1) if bucket[v]]  # 按下标扫描 = 已排好序
    print(len(unique))
    print(*unique)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 04:41
 * update_at: 2026-10-05 04:41
 */

// 明明的随机数：值域只有 [1,1000]，用桶数组去重 + 按下标扫描输出即有序。
#include <iostream>
typedef long long ll;
using namespace std;

const int MAXV = 1000;
int bucket[MAXV + 1]; // bucket[v] = 1 表示数字 v 出现过，重复写同一格即去重

int main() {
    ll n;
    cin >> n; // n 只决定读入多少个数，不参与计算
    for (ll i = 1; i <= n; i++) {
        ll v;
        cin >> v;
        bucket[v] = 1;
    }
    ll m = 0;
    for (int v = 1; v <= MAXV; v++) // 按下标从小到大扫，天然有序
        if (bucket[v])
            m++;
    cout << m << "\n";
    bool first = true; // 控制数字之间的空格
    for (int v = 1; v <= MAXV; v++)
        if (bucket[v]) {
            if (!first)
                cout << " ";
            cout << v;
            first = false;
        }
    cout << "\n";
    return 0;
}

目录

题目描述

思路

参考代码