P1059 [NOIP2006 普及组] 明明的随机数

· · 题解

题目传送门

勿喷，无注释代码在后面

分析题目

关于题目描述，只需要读两句话：1.他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N≤100) 2.请你协助明明完成“去重”与“排序”的工作。

本题解提供三种方法

方法一较麻烦

定义变量：n随机数个数,a[100010]随机数, b[10000010]桶排序,c去重后的长度,maxx最大值;

分析一下

剩下的就在代码里分析吧

#include<bits/stdc++.h>
using namespace std;
int n; //随机数个数 
int a[100010],b[10000010],c,maxx;//变量 
int main(){
    cin>>n;//输入个数 
    for(int i=0;i<n;i++){//循环 
        cin>>a[i];//输入 
        b[a[i]]+=1;//标记 
        if(b[a[i]]==1) c++;//标记长度：如果加完了刚刚=1那么就有这个数 
        maxx=max(maxx,a[i]);//最大值：因为我们使用桶排序，应遍历到最大值 
    }
    cout<<c<<endl;//输出长度 
    //            =!因为遍历到最大值，平时用int i=0;i<n的注意了！ 
    for(int i=0;i<=maxx;i++){//应遍历到最大值
        if(b[i]>0) cout<<i<<' ';//输出数 
    }
    return 0;//返回 
}

方法二还是较麻烦

既然我们只看有没有标记过，所以只有两个状态，1标记过2没有标记过，所以b数组可以使用bool类型 剩下的依旧在代码里分析吧

#include<bits/stdc++.h>
using namespace std;
int n;  //随机数个数 
int a[100010],c,maxx;//变量 
bool b[10000010];//桶 
int main(){
    cin>>n;//输入个数 
    for(int i=0;i<n;i++){//循环
        cin>>a[i];//输入
        b[a[i]]=1;//标记
        maxx=max(maxx,a[i]);//最大值：因为我们使用桶排序，应遍历到最大值 
    }
    //因为b是bool类型，所以无法用if(b[a[i]]==1) c++;，因为很容易重复 
    for(int i=0;i<=maxx;i++){//便利 
        if(b[i]) c++;//计数 
    }
    cout<<c<<endl;//输出长度
    //          是=!!!因为遍历到最大值，平时用int i=0;i<n的注意了！ 
    for(int i=0;i<=maxx;i++){//应遍历到最大值
        if(b[i]) cout<<i<<' ';//输出数 
    }
    return 0;//返回 
}

方法三简单

unique!!!

详细解释在这

在代码里分析吧

#include<bits/stdc++.h>
using namespace std;
int a[100010];//变量  
int n;//随机数个数 
int main(){
    cin>>n;//输入个数 
    for(int i=0;i<n;i++){//循环 
        cin>>a[i];//输入随机数 
    }
    sort(a,a+n);//排序 
    int len=unique(a,a+n)-a;//去重取长度 
    cout<<len<<endl;//输出长度 
    for(int i=0;i<len;i++){//便利 
        cout<<a[i]<<' ';//输出 
    }
    return 0;
}

无注释代码

方法一

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],b[10000010],c,maxx;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[a[i]]+=1; 
        if(b[a[i]]==1) c++;
        maxx=max(maxx,a[i]);
    }
    cout<<c<<endl; 
    for(int i=0;i<=maxx;i++){
        if(b[i]>0) cout<<i<<' ';
    }
    return 0;
}

方法二

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],c,maxx;
bool b[10000010];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
        b[a[i]]=1;
        maxx=max(maxx,a[i]);
    }
    for(int i=0;i<=maxx;i++){
        if(b[i]) c++;
    }
    cout<<c<<endl;
    for(int i=0;i<=maxx;i++){
        if(b[i]) cout<<i<<' ';
    }
    return 0;
}

方法三

#include<bits/stdc++.h>
using namespace std;
int a[100010]; 
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int len=unique(a,a+n)-a;
    cout<<len<<endl;
    for(int i=0;i<len;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

本人第一篇题解，求过