P1059 明明的随机数——题解

思路

数字范围只有 $1$ 到 $1000$，可以建立布尔数组 vis：

• 读到数字 x 时，把 vis[x] 设为真；
• 输入结束后，从 $1$ 到 $1000$ 顺序扫描；
• vis[i] 为真说明数字 $i$ 出现过，只统计和输出一次。

顺序扫描本身就完成了从小到大的排序。

复杂度

时间复杂度 $O(N+1000)$，空间复杂度 $O(1000)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

bool vis[1001];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        vis[x] = true;
    }

    int cnt = 0;
    for (int i = 1; i <= 1000; i++)
        if (vis[i]) cnt++;

    cout << cnt << '\n';
    bool first = true;
    for (int i = 1; i <= 1000; i++) {
        if (vis[i]) {
            if (!first) cout << ' ';
            cout << i;
            first = false;
        }
    }
    cout << '\n';
    return 0;
}

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