[NOIP 2006 普及组] 明明的随机数

知识点

去重、标记数组、桶排序

解题思路

建立1001个布尔标记，读到x就标记x出现。遍历1到1000统计出现过的数有多少个，再按同样顺序输出所有被标记的数。

正确性说明

输入值x的标记为真当且仅当它至少出现一次，重复出现不改变标记。按值从小到大扫描恰好输出每个不同值一次，因此同时满足去重与升序。

易错点

先输出不同数字个数，再输出数字；1000也是合法上界；原输入个数N可能大于不同数个数；相同值不能重复计数。

复杂度

时间O(N+1000)，空间O(1000)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;bool seen[1001]={};while(n--){int x;cin>>x;seen[x]=true;}int cnt=0;for(int x=1;x<=1000;++x)cnt+=seen[x];cout<<cnt<<'\n';bool first=true;for(int x=1;x<=1000;++x)if(seen[x]){if(!first)cout<<' ';first=false;cout<<x;}cout<<'\n';}