不重复地输出数

题目描述

输入格式：第一行一个整数 n（ $1 \leqslant n \leqslant 100000$ ），之后一行 n 个用空格分隔的整数，每个数在 int 范围内。输出格式：一行，从小到大不重复地输出这些数，相邻两个数之间用单个空格隔开。保证不同的数不超过 500 个。样例：输入 5 与 2 4 4 5 1，输出 1 2 4 5。

思路

数值范围是整个 int，按值域开桶会爆内存，所以按实际出现过的数组织：读入后放入 set，插入时自动去重，遍历时自动升序。依次输出 set 中的每个数即可，时间 $O(n \log n)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/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-30 01:33
# update_at: 2026-10-04 10:12

import sys


def solve() -> None:
    """读入 n 个整数，去重后升序输出。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                      # 题面的 n：只用来界定数据长度，去重后的个数由数据本身决定
    answer = sorted({next(data) for _ in range(n)})  # set 去重、sorted 升序，两个要求一次给全
    print(" ".join(map(str, answer)))


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/**
 * 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 06:55
 * update_at: 2026-10-05 06:55
 */

#include <cstdio>
#include <set>
#include <algorithm>
typedef long long ll;

const int MAXN = 100005;

ll a[MAXN]; // a[i]：第 i 个输入的数
int n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    // 值域是整个 int 范围，不能开桶；用 set 去重并自动保持升序
    std::set<ll> s(a + 1, a + n + 1);

    // 输出 set 里从小到大的每个数，相邻之间一个空格
    bool first = true;
    for (std::set<ll>::iterator it = s.begin(); it != s.end(); it++) {
        if (!first) printf(" ");
        printf("%lld", *it);
        first = false;
    }
    printf("\n");
    return 0;
}

目录

题目描述

思路

参考代码