摘要:本文主要向大家介绍了 C/C++知识点之c++ 内置函数,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了 C/C++知识点之c++ 内置函数,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
c++中有许多内置函数,当然,程序当中也可以自己定义。为了方便大家(还有我)查找如何使用,在做题中不断积累,本文也会不断更新。
1.unique() 去重函数
假设题目中有一数组 a ,要求将 a 从大到小输出,且相同元素只输出一个即可
做法:假设大家都知道 sort 这个东西(不知道的话,就随便写个排序吧),那就先 sort 一下,使元素按一定顺序(从大到小或从小到大)排列,然后:
int length= unique(/*跟sort里面几乎一样*/) - 数组名;
此处的 length 储存的是去重后数组的大小
unique 函数并非将相同的数字删去,而是将其移到了数组的最后面,如图:
2.sort() 快速排序
将数组的一部分进行排序 头文件:algorithm
核心代码(一般不需要记,可以直接调用):
void sort(int *a, int l, int r) {
//时间复杂度 递归式T(n) = O(n) + 2*T(n)
//即 O(nlogn)
swap(a[l], a[rand()*rand()%(r-l+1)+l]);
int tmp = a[l]; //右边的元素均小于tmp,左边的元素均大于tmp
int l_ = l, r_ = r;
while(l < r) { //循环的时间复杂度为区间长度
while(l < r) {
if(a[r] > tmp) r--; //a[r]落在正确的位置,不需要被调整
else { a[l++] = a[r]; break; }
}
while(l < r) {
if(a[l] < tmp) l++; //同上
else { a[r--] = a[l]; break; }
}
}
a[l] = tmp;
if(l-l_ > 1) sort(a, l_, l-1);
if(r-r_ > 1) sort(a, r+1, r_);
}
sort函数一般默认为从小到大排序,当需要将数组从大到小排序或要将结构体排序时,需要手写函数:
//数组从大到小排序
bool cmp1(int x, int y) {
return x > y; //从大到小排序
//return x < y; 从小到大排序
}
//结构体排序
struct node {
int w, id;
};
bool cmp2(node x, node y) {
//将结构体 x, y按照 w 从大到小排序,当 x,y 的 w 的值相等时,按照 id 从小到大拍
if(x.w == y.w) return x.id < y.id;
return x.w > y.w;
}
sort的应用:快速选择
int select(int *a, int l, int r, int k) {
swap(a[l], a[rand()*rand()%(r-l+1)+l]);
int tmp = a[l];
int l_ = l, r_ = r;
while(l < r) {
while(l < r) {
if(a[r] > tmp) r--; //a[r]落在正确的位置,不需要被调整
else { a[l++] = a[r]; break; }
}
while(l < r) {
if(a[l] < tmp) l++; //同上
else { a[r--] = a[l]; break; }
}
}
a[l] = tmp;
if(k == l-l_+1) return a[l];
if(k < l-l_+1) return select(a, l_, l-1, k); //比较tmp左边的元素
if(k > l-l_+1) return select(a, r+1, r_, k-(l-l_+1)); //比较tmp右边的元素
}
3.lower_bound() 及 upper_bound()
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号