整数去重

题目描述

给定长为 $n$ 的整数序列（ $1 \le n \le 20000$ ， $10 \le a_i \le 5000$ ），对每个值只保留首次出现位置，删除其余位置；输入第一行 $n$ 、第二行 $n$ 个整数；输出一行、用空格分隔，按原顺序排列。样例：5 / 10 12 93 12 75 → 10 12 93 75。

思路

值域仅 $5001$ ，按值当数组下标开布尔桶 seen；从左到右扫一遍，未出现过则保留并登记到紧凑前缀 keep，已出现过则跳过；时间 $O(n)$ 、空间 $O(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
26
27
28
29
30
31
32
33
34
35
36#!/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 19:48
# update_at: 2026-10-04 11:10

import sys

LIMIT = 5001  # 值域上界 5000 也必须是合法下标，所以表长取 5001 而不是 5000


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))                                  # 题面第一行：元素个数

    # seen 按「值」索引登记首次出现；keep 的第 k 格留给「第 k 个首次出现的值」的输出文本，
    # 「谁先出现谁占前面的格」正是本题要求的保序，故无需任何排序。
    seen = bytearray(LIMIT)
    keep = [b''] * LIMIT
    k = 0                                                # 已登记的首次出现个数 = 紧凑前缀长度

    for _ in range(n):                                   # 只取前 n 个 token，多余输入不理会
        token = next(data)
        x = int(token)
        if not seen[x]:                                  # 首次出现：登记，并落到前缀第 k 格
            seen[x] = 1
            keep[k] = token                              # 直接复用输入 token，省一次 str()
            k += 1
        # 非首次出现：什么都不做，等价于把该位置删掉

    sys.stdout.buffer.write(b' '.join(keep[:k]) + b'\n')


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
41
42
43
44
45
46
47/**
 * 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 02:25
 * update_at: 2026-10-05 02:26
 */
// main.cpp：稳定去重正解。按值索引开 bool 桶 seen，从左到右扫描，
// 首次出现的值保留并登记到 keep（紧凑前缀），天然保序且 O(n) 完成。

#include <cstdio>

typedef long long ll;

const int MAXV = 5001; // 值域上界 5000 也必须是合法下标，所以表长取 5001 而不是 5000

int n;                  // 输入序列长度
int a[MAXV];            // 读入的元素（n<=20000，足够装下）
int keep[MAXV];         // keep[k] = 第 k 个首次出现的值；[0, k) 即为输出
int seen[MAXV];         // seen[x] 标记值 x 是否已经在前面出现过：0 否 / 1 是
int k;                  // 已记录的首次出现个数 = 紧凑前缀长度

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

    k = 0;
    for (int i = 1; i <= n; ++i) {
        int x = a[i];
        if (!seen[x]) {          // x 还没出现过：保留并登记到前缀
            seen[x] = 1;
            keep[k] = x;
            ++k;
        }
        // 否则跳过，等价于删除该位置
    }

    for (int i = 0; i < k; ++i) {
        if (i) putchar(' ');
        printf("%d", keep[i]);
    }
    putchar('\n');

    return 0;
}

目录

题目描述

思路

参考代码