algorithm 头文件下的常用函数
1. max(), min()和abs()
//max(x,y)和min(x,y)分别返回x和y中的最大值和最小值，且参数必须时两个（可以是浮点数）
//返回3个数的最大数值可以使用max(x,max(y,z))
//abs(x)返回x的绝对值。
//浮点型的绝对值请用math头文件下的fabs
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int x = 1, y = -2;
printf("%d %d\n", max(x,y), min(x,y));
printf("%d %d\n", abs(x), abs(y));
return 0;
}
2. swap()
//swap(x,y)用来交换x和y的值
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int x = 1, y = 2;
swap(x, y);
printf("%d %d\n", x, y);
return 0;
}
3. reverse()
//reverse(it, it2)可以将数组指针在[it,it2)之间的元素或容器的迭代器在[it,it2)范围内的元素进行反转
//对元素进行反转
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[10] = {10, 11, 12, 13, 14, 15};
reverse(a, a + 4); //将a[0] ~ a[3]进行反转
for(int i = 0; i < 6; i++) {
printf("%d ", a[i]);
}
return 0;
}
//对容器中的元素进行反转
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
string str = "abcdefghi";
reverse(str.begin() + 2, str.begin() + 6); //对str[2] ~ str[5]反转
for(int i = 0; i < str.length(); i++) {
printf("%c", str[i]);
}
return 0;
}
4. next_permutation()
//next_permutation()给出一个序列在全排列中的下一个序列
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[10] = {1, 2, 3};
//a[0] ~ a[2]之间的序列需要求解next_permutation
do {
printf("%d%d%d\n", a[0], a[1], a[2]);
} while(next_permutation(a, a + 3));
return 0;
}
//使用循环是因为next_permutation在已经到达全排列的最后一个时会返回false
5. fill()
//fill()可以把数组或容器中的某一段区间赋为某个相同的值。
//和memset不同，这里的赋值可以是数组类型对应范围中的任意值。
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[5] = {1, 2, 3, 4, 5};
fill(a, a + 5, 233); //将a[0] ~ a[4]均赋值为233
for(int i = 0; i < 5; i++) {
pritnf("%d ", a[i]);
}
return 0;
}
6. sort()
//sort就是用来排序的函数，实际复杂度退化到O(n^2)
(1) 使用sort排序
sort(首元素地址(必填), 尾元素地址的下一个地址(必填), 比较算法(非必填));
//sort的参数有三个，其中前两个是必填的，而比较函数则可以根据需要填写
//如果不写比较函数，则默认对前面给出的区间进行递增排序
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[6] = {9, 4, 2, 5, 6, -1);
//将a[0] ~ a[3]从小到大排序
sort(a, a + 4);
for(int i = 0; i < 6; i++) {
printf("%d ", a[i]);
}
printf("\n");
//将a[0] ~ a[5]从小到大排序
sort(a, a + 6);
for(int i = 0; i < 6; i++) {
printf("%d ", a[i]);
}
return 0;
}
//double型数组排序
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
double a[] = {1.4, -2.1, 9};
sort(a, a + 3);
for(int i = 0; i < 3; i++) {
pritnf("%.lf", a[i]);
}
return 0;
}
//char型数组排序（默认字典序)
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
char c[] = {'T', 'W', 'A', 'K'};
sort(c, c + 4);
for(int i = 0; i < 4; i++) {
printf("%c", c[i]);
}
return 0;
}
(2) 如何实现比较函数cmp
//<1> 基本数据类型数据的排序
//对int型数组的排序
//默认从小到大排序
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[5] = {3, 1, 4, 2};
sort(a, a + 4);
for(int i = 0; i < 4; i++) {
printf("%d ", a[i]);
}
return 0;
}
//想要从大到小排序，则要使用比较函数cmp来告诉sort
//何时要交换元素（让元素的大小比较关系反过来）
#include <stdio.h>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) { return a > b; //当a > b时把a放在b前面}
int main() {
int a[] = {3, 1, 4, 2};
sort(a, a + 4, cmp);
for(int i = 0; i < 4; i++) {
printf("%d ", a[i]); //输出4 3 2 1
}
return 0;
}
//对doble型数组从大到小排序
#include <stdio.h>
#include <algorithm>
using namespace std;
bool cmp(double a, double b) {
return a > b;
}
int main() {
double a[] = {1.4, -2.1, 9};
sort(a, a + 3, cmp);
for(int i = 0; i < 3; i++) {
printf("%.lf ", a[i]);
}
return 0;
}
//char型数组从大到小排序
#include <stdio.h>
#include <algorithm>
using namespace std;
bool cmp(char a, char b) {
return a > b;
}
int main() {
char c[] = {'T', 'W', 'A', 'K'};
sort(c, c + 4, cmp);
for(int i = 0; i < 4; i++) {
printf("%c", c[i]);
}
return 0;
}
//<2> 结构体数组的排序
//定义结构体:
struct node {
int x, y;
} ssd[10];
//如果想将ssd数组按照x从大到小排序（即进行一级排序),那么可以这样写cmp函数
bool cmp(node a, node b) {
return a.x > b.x;
}
//示例：
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node {
int x, y;
} ssd[10];
bool cmp(node a, node b) {
return a.x > b.x; //按x值从大到小对结构体数组进行排序
}
int main() {
ssd[0].x = 2; //{2, 2}
ssd[0].y = 2;
ssd[1].x = 1; //{1, 3}
ssd[1].y = 3;
ssd[2].x = 3; //{3, 1}
ssd[2].y = 1;
sort(ssd, ssd + 3; cmp); //排序
for(int i = 0; i < 3; i++) {
printf("%d %d\n", ssd[i].x, ssd[i].y);
}
return 0;
}
//按x从大到小排序，但当x相等的情况下，按照y的大小从小到大排序(即进行耳机排序)
//cmp的写法：
bool cmp(node a, node b) {
if (a.x != b.x) return a.x > b.x;
else return a.y < b.y;
}
//cmp函数首先判断结构体内的x元素是否相等，如果不相等，则直接按照x的大小排序
//否则，比较两个结构体中y的大小，并按y从小到大排序
//示例：
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node {
int x, y;
} ssd[10];
bool cmp(node a, node b) {
if(a.x != b.x) return a.x > b.x; //x不等时按x从大到小排序
else return a.y < b.y; //x相等时按y从小到大排序
}
int main() {
ssd[0].x = 2; //{2, 2}
ssd[0].y = 2;
ssd[1].x = 1; //{1, 3}
ssd[1].y = 3;
ssd[2].x = 2; //{2, 1}
ssd[2].y = 1;
sort(ssd, ssd + 3, cmp); //排序
for(int i = 0; i < 3; i++) {
printf("%d %d\n", ssd[i].x, ssd[i].y);
}
return 0;
}
//<3> 容器的排序
//在STL标准容器中，只有vector, string, deque是可以使用sort的。
//set, map这种容器时用红黑树实现的，元素本身有序，故不允许使用sort排序
//示例：
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) { //因为vector中的元素为int型，因此仍然时int的比较
return a > b;
}
int main() {
vector<int> vi;
vi.push_back(3);
vi.push_back(1);
vi.push_back(2);
sort(vi.begin(), vi.end(), cmp); //对整个vector进行排序
for(int i = 0; i < 3; i++) {
printf("%d ", vi[i]);
}
return 0;
}
//string的排序
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string str[3] = {"bbbb", "cc", "aaaa"};
sort(str, str + 3); //将string型数组按字典序从小到大输出
for(int i = 0; i < 3; i++) {
cout << str[i] << endl;
}
return 0;
}
//按字符串长度从小到大排序
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(string str1, string str2) {
return str1.length() < str2.length(); //按string的长度从小到大排序
}
int main() {
string str[3] = {"bbbb", "cc", "aaa"};
sotr(str, str + 3, cmp);
for(int i = 0; i < 3; i++) {
cout << str[i] << endl;
}
return 0;
}
7. lower_bound()和upper_bound()
//lower_bound()和upper_bound()需要在一个有序数组或容器中。
//lower_bound(first, last, val)用来寻找在数组或容器的[first,last)范围内第一个值大于等于val的元素的位置
//如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器
//upper_bound(first, last, val)用来寻找在数组或容器的[first,last)范围内第一个值大于val的元素的位置
//如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器
//lower_bound()和upper_bound的复杂度均为O(log(last - first))
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[10] = {1, 2, 2, 3, 3, 3, 5, 5, 5, 5}; //注意数组下标从0开始
//寻找-1
int* lowerPos = lower_bound(a, a + 10, -1);
int* upperPos = upper_bound(a, a + 10, -1);
printf("%d, %d\n", lowerPos - a, upperPos - a);
//寻找1
lowerPos = lower_bound(a, a + 10, 1);
upperPos = upper_bound(a, a + 10, 1);
printf("%d %d\n", lowerPos - a, upperPos - a);
//寻找3
lowerPos = lower_bound(a, a + 10, 3);
upperPos = upper_bound(a, a + 10, 3);
printf("%d %d\n", lowerPos - a, upperPos - a);
//寻找4
lowerPos = lower_bound(a, a + 10, 4);
upperPos = upper_bound(a, a + 10, 4);
printf("%d %d\n", lowerPos - a, upperPos - a);
//寻找6
lowerPos = lower_bound(a, a + 10, 6);
upperPos = upper_bound(a, a + 10, 6);
printf("%d %d\n", lowerPos - a, upperPos - a);
return 0;
}
//如果只是向获得欲查元素的下标，就可以不使用指针，而直接令返回值减去数组首地址即可
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[10] = {1, 2, 2, 3, 3, 3, 5, 5, 5, 5};
printf("%d, %d\n", lower_bound(a, a + 10, 3) - a, upper_bound(a, a + 10, 3) - a);
return 0;
}