1172 明明的随机数
大约 3 分钟
1172 明明的随机数
【算法】 排序、去重
【C++】 sort、unique、一维数组
【难度】 入门
一、题目简述
明明用计算机生成了 个 到 之间的随机整数()。需要完成两件事:
- 去重:重复的数字只保留一个
- 排序:把去重后的数字从小到大排序
输出不相同的随机数的个数 ,以及排序后的这些数。
二、解题思路
2.1 数据规模分析
- ,数字范围
- 数据量极小,任何方法都能过
- 有两种经典做法
2.2 方法一:排序 + unique(推荐)
- 读入所有数到数组
sort排序unique去重(把不重复的元素移到数组前面,返回新的"尾后"位置)- 输出去重后的部分
sort(a, a + n);
int m = unique(a, a + n) - a; // 去重后元素个数2.3 方法二:桶计数
因为数字范围只有 ,可以用桶来标记出现过的数字:
bool bucket[1005] = {false};
for (int i = 0; i < n; i++) {
bucket[x] = true;
}然后遍历 ,输出所有 bucket[i] == true 的数。这种方法天然去重且有序,甚至连 sort 都不需要!
2.4 手动模拟
输入:
10
20 40 32 67 40 20 89 300 400 15方法一(排序+unique):排序后 → [15, 20, 20, 32, 40, 40, 67, 89, 300, 400],去重后 → [15, 20, 32, 40, 67, 89, 300, 400],共 8 个。
方法二(桶):遍历 ,输出有标记的数,共 8 个。
三、参考代码
3.1 排序 + unique(通用方法)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[105];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n); // 排序
int m = unique(a, a + n) - a; // 去重
cout << m << endl;
for (int i = 0; i < m; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
unique的原理:把不重复的元素依次放到数组前面,返回指向最后一个不重复元素的下一个位置的指针。减去a(数组首地址)就得到不重复元素的个数。unique不会真正删除元素,只是把重复的移到后面。
3.2 桶计数(范围小时最推荐)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
bool bucket[1005] = {false}; // 数字范围 1~1000
int cnt = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (!bucket[x]) {
bucket[x] = true;
cnt++;
}
}
cout << cnt << endl;
for (int i = 1; i <= 1000; i++) {
if (bucket[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}四、复杂度分析
| 方法 | 时间 | 空间 |
|---|---|---|
| 排序 + unique | ||
| 桶计数 | , |
两种方法对本题 都极快。桶计数法连排序都省了,代码更简洁。
五、易错点
- unique 不会改数组大小:
unique只是把重复元素挪到后面,返回的m是有效元素个数。遍历时要用i < m,不是i < n。 - 桶数组大小:数字范围 ,数组至少开 。不要只开 (那是 的上限,不是数字的上限)。
- 输出格式:第一行是 ,第二行是排序去重后的数,空格分隔。不要忘了换行。
五、知识扩展
5.1 手动实现 unique
int my_unique(int a[], int n) {
if (n == 0) return 0;
int j = 0;
for (int i = 1; i < n; i++) {
if (a[i] != a[j]) {
a[++j] = a[i];
}
}
return j + 1;
}思路:用 指向当前最后一个不重复元素的位置,遇到不同的就追加到 处。
