题目链接|明明的随机数

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $NN$ 个 $11$ 到 $10001000$ 之间的随机整数（ $N\le 1000N\backslash leq\; 1000$ ），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据(用于不同的调查)，希望大家能正确处理)。

简化版题意：有$NN$个$11$到$10001000$的随机数，去掉重复的之后进行排序。

方法一：使用数组标记出现过的随机数

利用哈希表的思想，遍历输入的$NN$个数字，对没出现过的数字在数组中标记为1，已出现过的数字忽略。由于这些数字都在$10001000$以内，所以可以在所有数字是否出现排查完之后，直接循环$11$到$10001000$（不需要额外排序），如果数组中标记着这个数字存在，则输出它。

时间复杂度：$O(N)O(N)$，解释：要输入$NN$个数字并进行记录，输出时也需要遍历$O(N)O(N)$大小的数组。

空间复杂度：$O(N)O(N)$，解释：需要$O(N)O(N)$大小的数组对数字是否出现进行记录。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int ans = 0;
int vis[1005] = {0};
int n;
int main() {
    while(cin >> n){ //多组输入
        memset(vis, 0, sizeof(vis)); //每组输入需要初始化标记的数组
        for(int i = 0;i < n;i ++){
            int val;
            cin >> val;
            int t = val;
            if(vis[t] == 0) { //如果当前数字没出现过
                vis[t] = 1; //标记该数字的出现
            }
        }
        for(int i = 0; i < 1005; i ++){ //直接按顺序循环输出
            if(vis[i]) {
                cout << i <<endl; //如果该数字存在就输出
            }
        }
    }
    return 0;
}

方法二：使用STL中的set

C/C++的STL中有set，可以直接利用并将所有数字添加到集合中。STL中的set会对添加的数字完成去重并从小到大排序。

时间复杂度：$O(Nlog(N))O(Nlog(N))$，解释：要输入$NN$个数字并进行记录，由于STL中set的实现是红黑树，单次添加的复杂度为$O(log(N))O(log(N))$，所以总复杂度为$O(Nlog(N))O(Nlog(N))$。

空间复杂度：$O(N)O(N)$，解释：需要$O(N)\mathrm{的}\mathrm{空}\mathrm{间}\mathrm{存}\mathrm{储}\mathrm{节}\mathrm{点}O(N)的空间存储节点$。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        set<int> sett; //创建集合
        int num;
        while (n--){
            cin >> num;
            sett.insert(num); //向集合中添加元素
        }
        for (auto r : sett){ //输出集合中的元素
            cout << r << "\n";
        }
    }
    return 0;
}