[NOIP2006]明明的随机数
[NOIP2006]明明的随机数
https://ac.nowcoder.com/acm/problem/16669
1、题目大意
明明用计算机生成了N个1到1000之间的随机整数（N ≤ 100），对于其中重复的数字，只保留一个，把其余相同的数去掉。然后再把这些数从小到大排序。请你协助明明完成“去重”与“排序”的工作。
2、思路分析
（1）数组标记。用数组is[i]标记i是否出现过。每读入一个x，观察x是否被is数组标记。若被is数组标记，忽略并进行下次数据的读入；反之读入数据将is[x]赋值为1并记录k的值。最后从1到k遍历a数组输出。
#include <bits/stdc++.h>
using namespace std;
int N,a[105],k;
bool is[105];
int main()
{
scanf("%d",&N);
for (int i = 1;i <= N;i++){
int x;
scanf("%d",&x);
if (!is[x]) a[++k] = x,is[x] = true;
}
sort(a + 1,a + k + 1);
cout << k << endl;
for (int i = 1;i <= k;i++) cout << a[i] << " ";
return 0;
}
（2）先对数组进行排序。然后从小到大遍历，若a[i] == a[i - 1]则不输出；反之则输出a[i]。
#include <bits/stdc++.h>
using namespace std;
int N,a[105],cnt;
int main()
{
scanf("%d",&N);
for (int i = 1;i <= N;i++) scanf("%d",&a[i]);
cnt = N;
sort(a + 1,a + N + 1);
for (int i = 1;i <= N;i++) if (a[i] == a[i - 1]) cnt--;
cout << cnt << endl;
for (int i = 1;i <= N;i++) if (a[i] != a[i - 1]) cout << a[i] << " ";
return 0;
}
（3）暴力搜索。对数列进行去重（没有标记的元素和他后面的元素两两比较，相同的则把后一个标记为不要），对去重之后的数组进行排序。
3、感悟
对于去重操作，目前来说比较常用的还是数组标记法，此法是以空间换时间的操作。后续如若还有相关去重策略，会相应在后续博客中总结，敬请期待。
联想公司氛围 153人发布
投递中国石油等公司10个岗位 >
查看8道真题和解析