【明明的随机数】 （C++代码）

解题思路:





注意事项:





参考代码:

看到大神们用的各种强大算法，蒟蒻我深感自己的渺小

第一种方法：

输入N，然后循环输入N个数：每输入一个数t，就把t存放到数组a的下标为t的单元。

存放时检测一下，假如a[t]==0则表示出现一个新的数据，则个数res自增1.

输出res，然后循环扫描a数组，假如哪一个元素不是0则输出该元素。

第二种方法：

也可以先输入N个数，然后排序

排序后相同的数应该聚集到一起。然后输出

输出时注意检测当前输出的元素跟前一个是否一致，一致则不输出。

这里选第一种方法，以空间换时间

献上本蒟蒻的代码

#include<iostream>//就是C++的基本库#include<cstdio>//这个不打NOIp会爆0using namespace std;int main(){
   freopen("random.cpp","r",stdin);//freopen，洛谷不要，but NOIp要！
   freopen("random.cpp","w",stdout);//freopen，洛谷不要，but NOIp要！
   int n,a[1001]={0},res=0,t;    cin>>n;//C可以用scanf("%d",&n);
   for(int i=0;i<n;i++)
   {        cin>>t;//C可以用scanf("%d",&t);
       if(a[t]==0)
       {
           a[t]=t;
           res++;
       }
   }    cout<<res<<endl;//C可以用printf("%d\n",res);
   for(int i=0;i<1001;i++)
   {        if(a[i]!=0)
       {            cout<<a[i]<<" ";//C可以用printf("%d ",a[i]);
       }
   }    return 0;//完美结束！！！}

欢迎大家关顾长郡郡维中学的官方博客：[长郡郡维中学官方博客](https://www.luogu.org/blog/cjjunwei/ "长郡郡维中学官方博客")

谢谢各位大佬对本人的关心！！！

评论

万振阳
桶排更好

评论

作者: lonelysir 更新时间: 2017-04-11 13:54  在Ta的博客查看  1 

本人的方法是，用一个数组记录1～1000中每个数有没有出现，如果出现过，让k加1，最后只输出一个。可以达到去重与排序的双重效果。

由于不知道末尾可以不输出空格，所以就用一个MAXN来记录最大值，当枚举到最大值，跳出循环，直接输出最大值，不带空格。

#include<iostream>#define bl -10using namespace std;bool b[1001]={false};int a[1001],n,maxn,k=0;int main(){
   maxn=bl;    cin>>n;    int i,j;    for(i=1;i<=n;i++)
   {        cin>>a[i];
       b[a[i]]=true;
       maxn=max(maxn,a[i]); //记录最大值
   }    for(i=1;i<=1001;i++)
   {        if(b[i])
       {
           k++; //记录总数
       }
   }
   cout<<k<<endl;    for(i=1;i<=1001;i++)
   {        if(i==maxn)
       {            break; //跳出循环
       }
       if(b[i])
       {            cout<<i<<" "; //只输出一次
       }
   }    if(b[maxn])
   {        cout<<maxn; //不带空格
   }    return 0;
}

评论

还没有评论

评论

作者: vonhyou 更新时间: 2017-01-30 20:16  在Ta的博客查看  1 

我们可以使用桶排序的思想，因为数据范围很小且都是正整数

#include<iostream>using namespace std;int main(){    int n,x;
   cin>>n;    int sum(0),bus[1002]={0};    for(int i=1;i<=n;i++){
       cin>>x;        if(bus[x])  //如果这个数已经出现过了，那么跳过
           continue;
       bus[x]++;  //如果没有出现，把数据放在桶里，并让总数居++
       sum++;
   }
   cout<<sum<<endl;    for(int i=1;i<=1000;i++)        if(bus[i])
           cout<<i<<' ';
   cout<<endl;    return 0;
}

评论

还没有评论

评论

作者: Fate_Ex 更新时间: 2016-09-04 17:02  在Ta的博客查看  1 

看到大家代码都好长，来个短一点的，使用简单的预处理将排序和去重一起做了

var
 i,x,n,ans:longint;
 c:array[1..10000]of boolean;begin
 readln(n);  for i:=1 to n do
 begin
   read(x);//输入数字
   c[x]:=true;//表示这个数出现了，而因为需要去重，所以不需要计算个数
 end;  for i:=1 to 1000 do
   if c[i]then inc(ans);//统计有哪些数出现过
 writeln(ans);  for i:=1 to 1000 do
   if c[i]then write(i,' ');//把出现过的数输出，由于从小到大判断，所以先输出的一定是小的，这里把排序也解决了end.

评论

还没有评论

评论

作者: cn：苏卿念 更新时间: 2017-12-21 20:42  在Ta的博客查看  0 

本宝宝强烈建议从后往前看

表示set是一个很好用的东西。没听说过的可以出门左转度娘。

set是一个可以去重并且以O(log n)O(logn)的复杂度插入元素，最后我们在找一遍有多少个数就好。直接上set的代码：

#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<set>//set需要这个头文件。using namespace std;set<int> s;//新建集合（set）set<int>::iterator it;//新建指针int n,x;//n表示共有几个数，x表示当前的数int now;//个数int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)
   {        scanf("%d",&x);
       s.insert(x);
   }//输入，插点
   for(it=s.begin();it!=s.end();it++)//找一遍有多少个数
       now++;
   printf("%d\n",now);//输出就好
   for(it=s.begin();it!=s.end();it++)    printf("%d ",*it);    return 0;//程序百拜拜}

好像很懵是吧。（刚才是什么鬼）

一个简单一点的方法：拿优先队列存，入队列的时候检查一下有没有在里面就好。那怎么判断是否在里面呢？数据范围这么小当然是bool数组呀！

#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<queue>//队列须要这个头文件。using namespace std;int n;int x;bool ins[1010];int ans;/*
n表示输入几个数，x还是当前的数，ins[i]表示的是i有没有在队列里，ans是还剩几个数。
*/priority_queue<int,vector<int>,greater<int> > q;//小根堆的优先队列int main(){      scanf("%d",&n);
     ans=n;//输入，初始化总共还剩n个数
     for(int i=1;i<=n;i++)
       {            scanf("%d",&x);//循环输入
           if(ins[x]==true)
           {
               ans--;//如果这个数之前已经有过了
               continue;//总数-1，跳过
           }            else
           q.push(x);//否则入队，标记
           ins[x]=true;
       }        printf("%d\n",ans);//按题意输出就好
       for(int i=1;i<=ans;i++)
       {            printf("%d ",q.top());
           q.pop();
       }    return 0;
}

其实数据范围让我很欣慰，所以来一个最简单最暴力的解法，就是直接爆搜。输入啥就标记，最后搜一遍标记了啥和有几个数就好

#include<cstdio>using namespace std;int n;int x;bool ins[1010];int sum;int ans[1005];
/*
n表示输入几个数，x还是当前的数，ins[i]表示的是i有没有在队列里，ans是最后的答案。sum是还剩几个数
*/int main(){    scanf("%d",&n);//输入
   for(int i=1;i<=n;i++)    scanf("%d",&x),ins[x]=true;//直接无脑标记
   for(int i=1;i<=1000;i++)    if(ins[i]) ans[++sum]=i;    //按照数据范围从头搜一遍就好。在的直接存。
   printf("%d\n",sum);//暴力输出
   for(int i=1;i<=sum;i++)    printf("%d ",ans[i]);    return 0;//程序拜拜}