这是一道经典的桶排序题目，利用数组来模拟桶，可以同时实现去重和排序。
1、先定义一个桶数组，保证题目给的每一个数据都有一个桶去装（为了防止越界，可以把数组开的大一点）
int tong[1005] = {}; // 题目数据最大是1000，所以数组大小就可以写成1005
这个桶数组用来装对应的每个数字，把这n个数据全部装到对应的桶里。(这里采用计数的方法，每装进一个数据，对应桶的值加1)
例如：第一个数据是20，就把这个数据装到下标为20的桶里，tong[20]++；第二个是40，就装到下标为40的桶里，tong[40]++
2、输入数据装到桶里：
int n; // 先获取数据的个数
cin>>n;
for(int i=1;i<=n;i++){ // 循环输入获取数据
int t;
cin>>t;
tong[t]++;
}
3、统计不重复的数字个数
已经将数据统计到桶里面，接下来去遍历整个桶，如果桶的值不为零，说明这个数字出现过，就计数一次（这样只会计算一次，不会重复），实现去重
int cnt = 0;
for(int i=1;i<=1000;i++){
if(tong[i] != 0) cnt++;
}
cout<<cnt<<endl; // 输出个数
4、输出数字
和上面同样的逻辑，这次换成输出数字。
因为桶只是用于统计次数的，所以我们真正要输出的是桶的下标（核心），下标从1开始，实现升序排序
for(int i=1;i<=1000;i++){
if(tong[i] != 0) cout<<i<<" ";
}
完整代码：
#include<iostream>
using namespace std;
int tong[1005] = {};
int main(){
int n; // 先获取数据的个数
cin>>n;
for(int i=1;i<=n;i++){ // 循环输入获取数据
int t;
cin>>t;
tong[t]++;
}
int cnt = 0;
for(int i=1;i<=1000;i++){
if(tong[i] != 0) cnt++;
}
cout<<cnt<<endl; // 输出个数
for(int i=1;i<=1000;i++){
if(tong[i] != 0) cout<<i<<" ";
}
return 0;
}
——————————————————————————————————————————————
上面的代码用了三个for循环，看上去好像有点麻烦，有没有更好的思路呢？
优化：
1、把上面的int数组换成bool数组；因为题目没有要求统计次数，所以计数没必要，只需要把计数变成标记就可以了。
出现的数字，把对应桶的值设置为1
例如：第一个数据是20，就把这个数据装到下标为20的桶里，tong[20] = 1；第二个是40，就装到下标为40的桶里，tong[40] = 1
bool tong[1005] = {};
int n; // 先获取数据的个数
cin>>n;
int cnt = 0; // 统计不重复数字的个数
for(int i=1;i<=n;i++){ // 循环输入获取数据
int t;
cin>>t;
if(tong[t]!=1){ // 只要这个数字第一次出现就标记，并且计数，后面再出现就不管了
tong[t] = 1;
cnt++;
}
}
cout<<cnt<<endl;
// 后面就是输出不重复的数字了，相信聪明的你可以做到（手动滑稽）
共 2 条回复
👍
👍