[JLOI2011] 不重复数字

题意

多组数据。删除数列中重复出现的数字，每个数字只保留第一次出现的位置，并按原顺序输出。

思路

集合能去重，但不能用来表达“保留第一次出现的顺序”。Python 字典会保留键的插入顺序，而同一个键再次插入不会改变原位置，所以：

python

1dict.fromkeys(values)

产生的键顺序恰好就是保序去重结果。数字保持为输入得到的 bytes，可直接 b" ".join(...)，无需先转 int 再转回字符串。

注意数据规模：T <= 50、n <= 5e4，总数可达约 2.5e6 个数。若每组都切片拷贝 token、或反复 print，容易在后几档数据 TLE（常见停在 60 分）。更稳的写法是：

一次 sys.stdin.buffer.read().split()；
用 islice(it, n) 顺序消费当前组，避免切片复制；
dict.fromkeys 保序去重；
stdout.buffer 批量写出。

Python 知识

dict.fromkeys(iterable) 用可迭代对象依次建立字典键。
Python 3.7 起，字典保持插入顺序是语言保证。
bytes 可哈希，因此既能做字典键，也能直接参与 b" ".join。
itertools.islice(it, n) 从迭代器取下一段，不创建中间列表拷贝。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：字典保序去重模式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字节串连接输出。

代码

Python：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import sys
from itertools import islice


def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    test_cases = int(next(it))
    out = []

    for _ in range(test_cases):
        n = int(next(it))
        # dict 保序去重；islice 避免切片复制整段 token 列表
        out.append(b" ".join(dict.fromkeys(islice(it, n))))

    sys.stdout.buffer.write(b"\n".join(out))
    sys.stdout.buffer.write(b"\n")


if __name__ == "__main__":
    main()

C++：用 unordered_set 记录出现过的数，边读边输出第一次出现的值，顺序自然保留。

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-06-21 13:41
 * update_at: 2026-07-19 11:35
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

int n;
int a[MAXN]; // 当前组输入

// 保序去重：第一次出现留下，后面重复丢掉
void solve_one() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    unordered_set<int> seen;
    bool first = true;
    for (int i = 1; i <= n; i++) {
        // 已经出现过，跳过
        if (seen.count(a[i])) {
            continue;
        }
        seen.insert(a[i]);

        if (!first) {
            cout << ' ';
        }
        cout << a[i];
        first = false;
    }
    cout << '\n';
}

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

    int T;
    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

注意：set 也能做，但有序集合插入是 $O(\log n)$ ，本题只需要“是否出现过”，哈希表更合适。unordered_set 不保证遍历顺序，所以不要靠遍历集合输出，而要按原数组顺序扫描，第一次见到再输出。

也可以使用 sort + unique，但要给每个数字带上原始下标：

按 (value, index) 排序，让同值中最早出现的排在最前面；
unique 按 value 去重，只保留第一次出现；
再按 index 排序，恢复题目要求的输出顺序。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * 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-19 11:49
 * update_at: 2026-07-19 11:49
 */
// main3.cpp：使用 sort + unique 保序去重的教学写法。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

struct Node {
    int value; // 数字本身
    int index; // 第一次输入时的原始位置
};

int n;
Node a[MAXN];

bool cmp_value_index(const Node &x, const Node &y) {
    if (x.value != y.value) {
        return x.value < y.value;
    }
    return x.index < y.index;
}

bool same_value(const Node &x, const Node &y) {
    return x.value == y.value;
}

bool cmp_index(const Node &x, const Node &y) {
    return x.index < y.index;
}

void solve_one() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].value;
        a[i].index = i;
    }

    // 先按 value 排，相同 value 按 index 排，让第一次出现的留在最前面。
    sort(a + 1, a + n + 1, cmp_value_index);

    // unique 只比较 value，相同数字只保留最早出现的那个。
    int new_n = unique(a + 1, a + n + 1, same_value) - (a + 1);

    // 再按原始位置排回去，恢复“第一次出现”的输出顺序。
    sort(a + 1, a + new_n + 1, cmp_index);

    for (int i = 1; i <= new_n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << a[i].value;
    }
    cout << '\n';
}

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

    int T;
    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

一组长度为 n 的数据，期望时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

“去重且保留第一次出现顺序”：Python 用 dict.fromkeys；C++ 用“原序扫描 + 哈希表判重”。两者都是 $O(n)$ 期望。

[JLOI2011] 不重复数字

目录

题意

思路

Python 知识

代码

复杂度

总结