蒜头君想在学校中请一些同学一起做一项问卷调查,为了确保实验的客观性,他先用计算机生成了n(1<=n<=100)个1到1000之间的随机整数,对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。 请你协助蒜头君完成“去重”与“排序”的工作。
共两行,第一行为一个正整数n。 第二行有n个用空格隔开的正整数,为所产生的随机数。
第一行输出一个正整数m,表示不相同的随机数的个数。第二行输出m个用空格隔开的正整数,为从小到大排好序的不相同的随机数。
10
20 40 32 67 40 20 89 300 400 15
8
15 20 32 40 67 89 300 400
首先,介绍一下两个函数~
sort函数用于C++中,对给定区间所有元素进行排序,默认为升序,也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n,比冒泡之类的排序算法效率要高,sort函数包含在头文件为#include< algorithm>的c++标准库中。
语法: Sort(start,end,cmp) 参数: (1)start表示要排序数组的起始地址; (2)end表示数组结束地址的下一位; (3)cmp用于规定排序的方法,可不填,默认升序。 sort类函数总结: sort 对给定区间所有元素进行排序 stable_sort 对给定区间所有元素进行稳定排序 partial_sort 对给定区间所有元素部分排序 partial_sort_copy 对给定区间复制并排序 nth_element 找出给定区间的某个位置对应的元素 is_sorted 判断一个区间是否已经排好序 partition 使得符合某个条件的元素放在前面 stable_partition 相对稳定的使得符合某个条件的元素放在前面
(一)实现按升序排列(没有cmp) 代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[100];
int n;
cin>>n;
for(int i = 0;i < n;i ++){
cin>>a[i];
}
sort(a,a+n);
for(int i = 0;i < n;i ++){
cout<<a[i]<<" ";
}
return 0;
}
结果:
(二)实现按降序排列
需要用到sort函数中的第三个参数啦~
加入比较函数compare(); 函数的实现过程如下:
bool compare(int a,int b){ return a>b;}
代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(int a,int b){
return a>b;
}
int main()
{
int a[100];
int n;
cin>>n;
for(int i = 0;i < n;i ++){
cin>>a[i];
}
sort(a,a+n,compare);
for(int i = 0;i < n;i ++){
cout<<a[i]<<" ";
}
return 0;
}
结果:
unique的作用是“去掉”容器中相邻元素的重复元素,“去掉”本质是将重复的元素移动到数组的末尾,最后再将迭代器末尾指向最后不重复的下标。也包含在头文件为#include< algorithm>的c++标准库中。
一般使用前需要对容器进行排序,这样才能实现对整个数组去重。 代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[100];
int n;
cin>>n;
for(int i = 0;i < n;i ++){
cin>>a[i];
}
int m = unique(a,a+n)-a;
cout<<m<<endl;
for(int i = 0;i < m;i ++){
cout<<a[i]<<" ";
}
return 0;
}
结果:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[100];
int n;
cin>>n;
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 ++){
if(i == m-1) cout<<a[i];
else cout<<a[i]<<" ";
}
return 0;
}