CodeVs 1075 明明的随机数（ C语言和java两种方式和思路）
CodeVs 1075 明明的随机数（ C语言和java两种方式和思路）
题目：
1075 明明的随机数
2006年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 白银 Silver
题目描述 Description
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入描述 Input Description
有2行，第1行为1个正整数，表示所生成的随机数的N个数：
第2行有N个用空格隔开的正整数，为所产生的随机数
输出描述 Output Description
第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小
到大排好序的不相同的随机数。
样例输入 Sample Input
10
20 40 32 67 40 20 89 300 400 15
样例输出 Sample Output
8
15 20 32 40 67 89 300 400
读完题目，大部分人想到的方法是——完成输入后，进行两个步骤，第一：对当前数组进行去重（去掉重复值）处理；第二：对当前数组进行排序处理。这两个步骤的顺序无所谓，都可以。
接下来先按照这种方法，用java语言完成一下（具体思路会在代码的注释中体现）——
package com.zyc.Arithmetic;
import java.util.Scanner;
/**
* ------------------------------------
* Create with IntelliJ IDEA
* Author:Pink Panther
* Date:2018/6/19
* Time:14:36
* To change this template use File | Settings | File Templates.
*/
public class codevs_1075 {
public static void main(String[] args) {
Scanner sc=new Scanner (System.in);
while (sc.hasNext ()) {
//输入
int m = sc.nextInt ();//把键盘输入的第一个数赋给m，m为输入的元素的个数
int[] a = new int[m];//声明并开辟一个大小为m的数组a
for (int i = 0; i < m; i++) {//接收键盘输入，每输入一个数，存到数组a中
a[i] = sc.nextInt ();
}
//去重处理
for(int i=0;i<m;i++)
{
for(int j=i+1;j<m;j++)//j：查找重复元素的位置
{
if(a[i]==a[j])//找到重复元素，用该数后面的数去覆盖它
{
for(int k=j+1;k<m;k++)//k：用于覆盖处理
{
a[k-1]=a[k];
}
m--;//每找到一个重复元素，数组的长度都会减一，所以要记得m--操作
}
}
}
//排序处理（这里用的是冒泡排序，博客里写过，就不多说了）
for(int i=0;i<m;i++)
{
for(int j=0;j<m-1-i;j++)
{
if(a[j]>a[j+1])
{
int temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
//输出
System.out.println (m);
for (int i = 0; i < m; i++) {
System.out.print (a[i] + " ");
}
}
}
}
运行结果如下图：
这种方法可以完成对数组的去重和排序，但是程序有些复杂，思路也很常规。接下来，我们将用到一种很巧妙的方法来完成这个程序——用到了桶排序的思想，不过这种方法比较消耗内存。
我们注意到题目中说到，生产的随机数范围是1——1000，那么，我们创建一个一个大小为1000的数组a，该数组的下标对应的就是随机数的值，每放入一个随机数，就对对应的下标的值加1。要注意的是，当遇到重复的随机数，仍然保持下标对应的值为1，不发生改变。
这样的话，我们在输出去掉重复值后，数组中元素的个数的时候，只需要统计一下a[1000]里面，下标对应的值为1，出现的次数即可。在输出去掉重复值后，数组中元素的时候，只需要按照顺序，输出——元素的值为1时（证明该随机值出现过），对应的下标的值即可（下标的值为随机数的值，因为下标是有序的，所以我们放入的元素，已经是有序的了）。
下面就用C语言来实现一下吧——
#include<stdio.h>
int main()
{
int N,n,count=0,i;
scanf("%d",&N);
int a[1000] = { 0 };
while (N--) {
scanf("%d",&n);
a[n] = 1;
}
//统计不重复的元素的个数
for (i = 0; i < 1001; i++)
{
if (a[i]==1)
{
count+=1;
}
}
printf("%d\n",count);
//输出有序且不重复的元素
for (i = 0; i < 1001; i++)
{
if (a[i]==1)
{
printf("%d ",i);
}
}
return 0;
}
这个我已经提交过，测试通过AC。