STL中的unique()和lower_bound ,upper_bound
unique():
作用:unique()的作用是去掉容器中相邻元素的重复元素(数组可以是无序的,比如数组可以不是按从小到大或者从大到小的排列方式)
使用方法:unique(初始地址,末地址);
这里要注意的是:
1.unique()函数返回值不是去重后容器中元素的数量,而是去重后容器中的末地址。也就是说,如果想得到去重后容器中元素的数量的话还要减去初始地址。
2.unique函数在去重的时候不会扔掉重复元素,而是会把它放在容器的末尾,也就是说数组的长度一直没有变化。
举一个例子:
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(){
int n;
cin>>n;
int a[n+];
for(int i=;i<=n;i++){
cin>>a[i];
}
sort(a+,a++n,cmp);
int m=unique(a+,a++n)-(a+);
cout<<m<<endl;
return ;
}
跑一下下面的程序:
#include<bits/stdc++.h>
using namespace std; int main(){
int n;
cin>>n;
int a[n+];
for(int i=;i<=n;i++){
cin>>a[i];
}
sort(a+,a++n);
for(int i=;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
int m=unique(a+,a++n)-(a+);
cout<<m<<endl;
for(int i=;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return ;
}
会发现,其实unique之后的数组的长度一直没有变,然后去重了之后数组的最后几位会变成原来排序后的数组的最后几位。
看运行结果:
5
4 6 9 9 4 // 输入的数组
4 4 6 9 9 // 排序后的数组
3 //去重后的值
4 6 9 9 9 //去重后数组的内容
由于去重了两个数字,所以去重后的数组最后两位和排序后数组的最后两位相同。
10
3 3 3 3 5 9 7 2 1 9
1 2 3 3 3 3 5 7 9 9
6
1 2 3 5 7 9 5 7 9 9
这个案例也是如此
STL中还有函数 lower_bound,upper_bound。
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
程序如下:
#include<iostream>
#include<algorithm>
using namespace std;
int a[]={,,,,};
int main(){
sort(a,a+);
int t1=lower_bound(a,a+,)-a;
int t2=upper_bound(a,a+,)-a;
cout<<t1<<endl;
cout<<t2<<endl;
return ;
}
运行结果:
2
3
最新文章
- hdu 1028 Ignatius and the Princess III 简单dp
- win7家庭版更改桌面图标
- UVa 11427 - Expect the Expected
- vs2010 release 模式加了断点,跑代码无法跟踪,解决方法
- autoit UIA获取Listview的信息
- cmake的使用二:链接第三方静态库
- php 开发最好的ide: PhpStorm
- 理解TCP可靠的通信
- ZStack中的编程技巧
- HW5.2
- ASCII 码表对照 2
- bit和sbit的区别
- 正则匹配<;img src=";xxxxxx"; alt=";"; />;标签的相关写法
- cocos2dx CCControlButton button大事
- Spire PDF for .NET 在ASP.NET中的使用 ---- 并非那么“美好”,有些挫折!
- angular自定义验证 ngModel的一些理解
- HDU 4333 Revolving Digits [扩展KMP]【学习笔记】
- 开篇/javascript基础知识点
- Gitlab管理网页老是500错误?增加物理内存,增加cpu吧
- C# winfrom 通过代码 删除TableLayoutPanel控件的一行或列