明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客 观性，他先用计算机生成了N个1到1000之间的随机整数 （N≤100），对于其中重复的数字，只保留一个，把其余相同的 数去掉，不同的数对应着不同的学生的学号。然后再把这些数从 小到大排序，按照排好的顺序去找同学做调查。请你协助明明完 成“去重”与“排序”的工作。 输入格式 输入2行，第1行为1个正整数，表示所生成的随机数的个数： N 第2行有N个用空格隔开的正整数，为所产生的随机数。 输出格式 输出也是2行，第1行为1个正整数M，表示不相同的随机数的个 数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相 同的随机数。 样例1 输入： 10 20 40 32 67 40 20 89 300 400 15 输出： 8 15 20 32 40 67 89 300 400
非比较的排序思想
上节课我们学习了冒泡排序和选择排序，这是两种比较入门的排 序。排序的算法很多，有书写的难易之分，也有其他维度的划 分。冒泡排序和选择排序都是基于比较的。 基于比较的意思很好理解，不管使用什么样的排序策略（选择排 序的策略是找剩余区间的最值和未排序的首个元素进行交换，冒 泡排序的策略是相邻元素两两比较），算法在最终实施时都是基 于最朴素的比较和交换。 这次我想给你讲讲不基于比较的排序思路。不基于比较的排序方 法写起来更加巧妙，效率也很高，但是对未排序的数据有严格的 要求。考虑一下下面的案例： 1.某省今年参加高考的考生人数是 100 万，对这一百万考生的成 绩做一个排名，使得每个考生能快速查询自己的成绩在全省的排 名。 2.中国有 14 亿人口，大规模人口普查后，想要对国民的年龄做一 个排序，以便判断中国是否进人了人口老龄化的阶段。 … 上面的例子的共同特征：数据的范围比较小，考分无外乎 0-900 ，人类的寿命基本 0-200 差不多够用了。 那么就可以引出另一类非比较的排序，常见的代表：桶排序、计 数排序和基数排序。
桶排序思想
桶排序其实是介于比较排序和非比较排序的过渡体。核心思想是 引入新的数组，把原本的数据分配到新的数组中，以达到缩小数 据规模的目的。我们管这些新数组叫做“桶”，桶按照数据范围均 匀划分，且本身就是有序的，比如有一万个数字，但是数字的范 围是1-50，那么我们就可以新建5个数组，每个数组只保存对应范 围内的数字，范围如下： [1,10] [11,20] [21,30] [31,40] [41,50] 然后遍历这一万个数，把其中的每个数字都划分到合适的桶内， 这样每个桶内的数字总量就减少了很多，如果原数据均衡的话， 每个桶平均只有2000个数字，相比原来的一万个数字，排序起来 高效了很多。 对每个桶单独使用常规的基于比较的排序后，每个桶内的数据就 都是有序的了，按照桶的先后顺序把内部的数据拼接起来后就是 排好序的一万个数字了。 计数排序是桶排序思想的特殊情况，因为计数排序的“桶”的容量 为 1，回归到这个题目中，因为数据的范围是 1 到 1000，满足非 比较排序的应用条件，刚好还有去重的需求，用“桶”简直是不能 再合适了。 依照计数排序的思想，新建一个长度为 1001 的数组，这就是我 们的“桶”。元素初始值均为 0。具体的解法请参考下面的示例代 码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
//n是数据总数，num 是当前数字，cnt 是去重后的数量，nums
是计数的桶
int n,num,cnt = 0,nums[1001] = {0};
cin>>n;
for(int i = 1;i <= n;i++) {
cin>>num;
//某个数字第一次出现，cnt计数增加。
if(nums[num] == 0)
cnt++;
// nums[num] 保存的是某个数字出现的总次数。
nums[num]++;
}
cout<<cnt<<endl;
//统计完了，计数排序的桶容量为1，且是有序的，自带排序功
能，按顺序输出就行了
for(int i = 1;i <= 1000;i++) {
//数字i出现过
if(nums[i] != 0) {
cout<<i;
cnt--;
//cnt 不为 0 说明数字还没有打印完
if(cnt != 0) {
cout<<" ";
} else {
//cnt 为 0 说明数字已打印完毕，可以直接结束程
序了
return 0;
}
}
}
return 0;
}
最后再补充几句，虽然这个题已经解决了，但是上面的解法并不 是完整的“计数排序”，只是借用了计数排序的桶格式，以及桶的 第一步填充，要实现完整的计数排序，后面还有很多步骤，难度 Comments 比较高我就不再介绍了。不管用哪种排序方法，得到完整的有序 数据，并且把这些数据存到数组中才是排序，比如这题的样例， 排序后数组中的元素是： 15 20 20 32 40 40 67 89 300 400 才能称之为排序，由此可见，题目的要求已经帮我们简化了不少 工作量了。