复杂度
-
1GhzCPU的1s大约运算1e8次，n(1e8)，n²(10000)，n³(500)，2^n(27)
-
n!的弱上界n^n
-
-
开数组的时候，a[1e9] , 约为2^32，超过1G内存，堆没有那么大，会堆溢出（1e8 ≈ 2^27）
动态创建数组
静态分配（从进程空间/虚拟地址来看是连续的，实际物理内存不一定连续）
- 函数中使用数组：栈，最大空间4M
- 全局数组：静态存储区
动态分配（new/malloc）：堆
https://zhuanlan.zhihu.com/p/134239145
#include <stdlib.h>
// 一维数组
int *a = NULL;
a = (int *)malloc(len * sizeof(int));
free(a);
// 二维数组
int **a = NULL;
a = (int **)malloc(len * sizeof(int *));
for(int i = 0;i < len;i ++){
a[i] = (int *)malloc(llen * sizeof(int)); // 多个a[i]的地址可能不连续
}
for(int i = 0;i < len;i ++)free(a[i]);
free(a);
#include <iostream>
using namespace std;
// 一维数组
int *a = new int[len];
delete[] a;
// 二维数组
int **arr = new int *[len];
for (int i = 0; i < len; i++){
arr[i] = new int[llen];
}
for(int i = 0;i < len;i ++)delete[] arr[i];
delete[] arr;
STL
vector: https://www.cnblogs.com/youpeng/p/10779019.html
set: https://blog.csdn.net/weixin_42522886/article/details/87450083
二分查找
//查找某个元素是否出现
bool binary_search(arr[],arr[]+size,target)
//返回一个迭代器，指向非递减序列[first, last)中的第一个>=val的位置
lower_bound(beg,end,val)
//返回一个迭代器，指向非递减序列[first, last)中的第一个大于>val的位置
upper_bound(beg,end,val)
int a[] = {1,2,3,3,3,4,4};
cout << binary_search(a,a+7,3.5) << endl; //0
cout << lower_bound(a,a+7,3)-a << ":" << *lower_bound(a,a+7,3) << endl;//2:3,即第一个3
cout << upper_bound(a,a+7,3)-a << ":" << *upper_bound(a,a+7,3) << endl;//5:4,即第一个4
//迭代器
std::vector<int> vec{1,2,3,4,4,4,5,6};
std::vector<int>::iterator it1 = std::lower_bound(vec.begin(), vec.end(), 4);
max_element(beg,end) //vector返回迭代器
min_element(beg,end)
int *maxNum = max_element(a,a+len);
sort
当数据量大时，将会采用Quick Sort（快排），分段递归进行排序。一旦分段后的数据量小于某个阈值，为了避免快排的递归带来过大的额外的开销，sort()算法就自动改为Insertion Sort（插入排序）。如果递归的层次过深，还会改用Heap Sort（堆排序）。
sort(begin,end,cmp); //自实现cmp函数：int cmp(int a,int b); return 1,-1,0;
sort(begin,end,less<type>()); //升序，默认
sort(begin,end,greater<type>()); //降序
//字符串中字符排序
string str("hello world");
sort(str.begin(),str.end());
//结构体排序
struct link {
int a,b;
};
bool cmp(link x,link y)
{
if(x.a==y.a)
return x.b>y.b;
return x.a>y.a;
}
或：
//按从大到小排序
struct Rule1 {
bool operator()( const int & a1,const int & a2) {
return a1 > a2;
}
};
partial_sort
//部分排序，相当于小根堆
partial_sort(beg,sortEnd,end)
partial_sort(beg,sortEnd,end,op)
//对区间[beg,end)内的元素进行排序，使区间[beg,sortEnd)内的元素处于有序状态
partial_sort_copy 对给定区间复制并排序
is_sorted
bool is_sorted(begin,end);
partition
bool IsOdd(int i) {
return (i%2 == 1);
}
vector<int>::iterator bound;
bound = partition(v.begin(), v.end(), IsOdd);
map
key不允许重复，插入key相同的键值对不报错但后插入的无效+红黑树实现
#include <map>
//增
1.mymap.insert(pair<string,int>("cq",1997));
2.mymap["CQ"]=1997; //这种插入效率不高。
//它会执行3个操作，首先检查键值"CQ"是否存在，如果存在，则会修改value为1997；否则插入键值为CQ的pair，此时value为空；最后再将value改成1997
map<string,int>::iterator it = mymap.find(key);
if(it != mymap.end()){ //查
cout << it->second;
it->second = 1; //改
mymap.erase(it); //删
}
mymap.clear(); //删除所有元素
mymap.empty();
mymap.size();
//遍历
map<int, int>::iterator iter = _map.begin();
while(iter != _map.end()) {
cout << iter->first << " : " << iter->second << endl;
iter++;
}
set
key不允许重复+红黑树实现+ 根据元素的值自动进行排序(基于小于关系)+元素值不能被改变
#include <set>
//创建
--1.基本类型
set<int> a[100];
set<string> myset = {1,2,3};
set<int> s3(s1); //拷贝
--2.自定义类型
typedef struct node{
int val;
bool operator<(const node& b) const {
return this->val < b.val;
} //自定义类型需重载<
}Node;
set<Node> s;
//增
myset.insert();
Node tmp;
tmp.val = 1;
s.insert(tmp);
cout << s.size() << endl; //1
tmp.val = 2;
s.insert(tmp);
cout << s.size() << endl; //2，同一个对象，类似于拷贝构造
set<int>::iterator iter = myset.find(key);
if(it != mymap.end()){ //查
cout << *it << endl; //基本类型
cout << (*it).val << endl; //自定义类型
myset.erase(it);
myset.erase(key); //删值为key的节点
}
myset.clear(); //删除所有元素
myset.size();
myset.empty();
优先队列
struct cmp{
bool operator()(ListNode* a,ListNode* b){
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
for(int i = 0;i < lists.size();i ++){
if(lists[i]!=NULL)heap.push(lists[i]);
}
ListNode* head = new ListNode();
ListNode* p = head;
while(!heap.empty()){
ListNode* tmp = heap.top();
heap.pop();
p->next = tmp;
p = p->next;
if(tmp->next!=NULL)heap.push(tmp->next);
}
return head->next;
}
算法模板
字符串处理
char[]
基本用法
char s[] = "c++ is good"; //手动处理末尾'\0'
cin>>s; scanf("%s",s); gets(s); //puts(s)行末有换行符
scanf("%s",s+1); printf("%s",s+1); //从s[1]开始存储或输出
int len = sizeof(s); //开辟空间的大小
int len = strlen(s); //有效字符数
//写成for(int i=0;i<strlen(s);i++)速度会慢很多，每次要strlen
strcat(s1,s2); //注意s1要足够大能够容纳所有字符
strcpy(s1,s2); //注意s1要足够大能够容纳所有字符
strcmp(s1,s2); //s1>s2返回1,s1<s2返回-1
//转化为string
string sstr(cstr); string sstr = cstr; //相互等价
string sstr(cstr,10); //前10个字符作为字符串sstr的初值
数字和字符串相互转换
//int转char[]
int num = 30;
char s[8];
int len = sprintf(s, "%05X", num); // 16进制
//TODO...(s)
//char[]转int
int num;
sscanf("17", "%D", &num);
//TODO...(num)
string
基本用法
string s = "NOIP"; //string可用[]索引和修改(若本来不存在元素就不能修改)
string s1 = s; //string之间可以相互赋值
swap(s1,s2);
s1+=s2;//尾部添加，s2可以是string,char[],char
s1.replace(begin,num,s2); //s1[begin]~s1[begin+num]替换为s2
s1.length();
><=!=比较string
bool s1.empty()
//转化为char[]
char cstr[] = s.c_str();
数字和字符串相互转换
#include <sstream> //bits/stdc++.h包含该头文件
//int转string
int number = 12;
string str;
stringstream ss;
ss<<number; //流入数据
ss>>str; //流出数据
ss.clear(); //清除流中残留的数据
//TODO...(str)
//string转int
string str = "13";
int num;
ss<<str2;
ss>>num;
ss.clear(); //清除流中残留的数据
//TODO...(num)
并查集
//查询并进行路径压缩
int getfather(int x){
int tmp = x, x_father;
while(tmp != father[tmp])tmp = father[tmp];
x_father = tmp;
tmp = x;
while(father[tmp] != x_father){
int temp = father[tmp];
father[tmp] = x_father;
tmp = temp;
}
return x_father;
}
cnt = m*n;
while(k --){
cin >> a >> b;
int a_father = getfather(a);
int b_father = getfather(b);
if(a_father != b_father){
father[a_father] = b_father;
cnt --;
}
}
cout << cnt << endl;
着色问题
相邻两点不能着同一种颜色，问至少需要多少种颜色
int n, k;
int adj[N][N]; //关系表
int p[N][N]; //p[i][j]:涂第i种颜色第j个点编号
int min_cos; //使用最少颜色种数
void DFS(int x,int cos){ //当前给第x个点染色，已经用了cos种颜色
if(cos >= min_cos)return; //剪枝
//已经为所有点涂完色
if(x == n+1){
if(min_cos > cos)min_cos = cos;
return;
}
//第一种：用过的颜色涂
for(int i = 1;i <= cos;i ++){
int k = 1;
while( p[i][k] && !adj[p[i][k]][x] )k ++;
//如果有冲突进下一次循环
//如果没有冲突:
if(!p[i][k]){
p[i][k] = x; //用第i种颜色涂
DFS(x+1,cos);
p[i][k] = 0; //回溯
}
}
//第二种：新用一种颜色涂
p[cos+1][1] = x;
DFS(x+1,cos+1);
p[cos+1][1] = 0; //回溯
}
DFS(1,0)
位运算
Tip
>>>用0填充高位，>>用符号位填充- int型(32bit)x，x<<(32+a) = x<<a，编译器自动减32, long型同理
- 异或
^,+- 不进位加法:1+1=0,0+0=0,1+0=1
a^0=a,a^a=0,a^1=各位取反- 异或的一个重要功能是消除重复:
A^A^B^C^C=B (a^b)^c = a^(b^c)
- 算术运算符优先级比位运算符高, 涉及位运算的地方都加上括号
int mid = low + ((up-low)>>1);
判断奇偶数
x & 1 == 1 // 奇数
x & 1 == 0 // 偶数
获取二进制位
//方案1
( (x&(1<<(y-1)) )>>(y-1) ) == 0 ? "0":"1"
// x&(1<<(y-1))清零除右往左数第y位以外的数据,然后再右移回去
//方案2
(x>>(y-1)) & 1) == 0 ? "0":"1"
交换两个整数
a = a ^ b; //a1 = a0 ^ b0
b = a ^ b; //b1 = a1 ^ b0 = a0 ^ b0 ^ b0 = a0
a = a ^ b; //a2 = a1 ^ b1 = a0 ^ b0 ^ a0 = b0
求整数的绝对值
(a ^ (a >> 31)) - (a >> 31)
//解析:
若a为正数则a >> 31 = 00000000 00000000 00000000 00000000
若a为负数则a >> 31 = 11111111 11111111 11111111 11111111
正数的原码,反码,补码均相同
负数的反码是将其原码除符号位之外的各位求反,补码是反码加1
/*
若a为正数,(a^(a>>31)) - (a>>31) = (a^0)-0 = a,满足正数的绝对值就是本身
若a为负数,(a^(a>>31)) - (a>>31)为各位取反再减-1,即各位取反加1
以-13为例:
原码:10000000 00000000 00000000 00001101
反码:11111111 11111111 11111111 11110010
补码:11111111 11111111 11111111 11110011(-13在计算机中实际存储格式)
//System.out.println(Integer.toBinaryString(-13));
对补码各位取反加1:00000000 00000000 00000000 00001101(13)
*/
找出成对的数
1-1000这1000个数放在1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将重复元素找出来；不用辅助存储空间
思路:(a[1]^...k...k...^a[1000])^(1^2...^999^1000) = k , 运用异或的消除重复功能
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5};
int x = 0;
for (int i = 0; i < arr.length; i++) {
x = x ^ arr[i];
}
for (int i = 1; i < arr.length; i++) {
x = x ^ i;
}
System.out.println("数组中唯一重复的数是：" + x);
}
}
二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例：9的二进制表示为1001，有2位是1。
//思路1:依次判断每一位
for(int i = 0;i < 32;i ++) {
if( (x&(1<<i))>>i == 1)count ++;
}
//思路2:将原数不断右移,判断低位
for(int i = 0;i < 32;i ++) {
if( ((x>>i))&1 == 1 )count ++;
}
//思路3:
x-1:x二进制低位第一个1变为0,该位后面的0变为1
x&(x-1):清零x二进制低位的第一个1
int a = x;
while(a != 0){
a = a&(x-1);
count ++;
}
拓展：判断一个数是不是2的整数次方
if((x-1)&x == 0)
将整数的奇偶位互换
将一个整数的二进制位上的1与0做交换。以低位为第1位的话，即将第1位(奇位)与第2位(偶位)互换，第3位(奇位)与第4位(偶位)互换，... 。如 00..0..0_1001(9)，互换后为 00..0..0_0110(6)
思路1：每一位用数组存储起来,依次循环交换
思路2：
//int odd = 0b0101_0101_0101_0101_0101_0101_0101_0101;
int odd = x & 0x55555555;
int even = x & 0xaaaaaaaa;
return (odd<<1)^(even>>1);
0~1间浮点数的二进制表示
给定一个介于0和1之间的实数，如（0.625），类型为double，打印它的二进制表示（0.101，因为小数点后的二进制分别表示为0.5 , 0.25, 0.125…).
如果该数字无法精确的用32位以内的二进制表示，则打印“ERROR”。
思路： 每次将x乘2，如果整数部分为1，则在二进制表示的后面加1，否则加0，然后x挪去整数部分。 循环，直到x为0结束。 如：(x=0.625, x=1.25, b=0.1..., x=0.25) , (x=0.25, x=0.5, b=0.10..., x=0.5) , (x=0.5, x=1.0, b=0.100..., x=0.0), x=0.0结束
public class Main {
public static void main(String[] args) {
double x = 0.625;
StringBuilder sb = new StringBuilder("0.");
while (x > 0) {
x = x * 2;
if (x >= 1) {
sb.append("1");
x = x - 1;
} else {
sb.append("0");
}
if (sb.length() > 34) {
System.out.println("ERROR");
return;
}
}
System.out.println(sb.toString());
}
}
出现k次和出现1次
数组中只有一个数出现了1次，其他的数都出现了K次，请输出只出现了一次的数
思路：k个相同的k进制数作不进位加法结果为0，将这个数组中所有的10进制整数均转化为k进制数，把所有的k进制数加起来，出现k次的数字会抵消，最后加法的结果即为出现1次的那个数的k进制表示，转回10进制
两个相同的二进制数作不进位加法（如3）：
0 1 1
0 1 1
------
0 0 0
三个相同的三进制数作不进位加法（如4,4 = 1*3^1 + 1*3^0）:
0 1 1
0 1 1
0 1 1
------
0 0 0
#include <bits/stdc++.h>
using namespace std;
//十进制数转radix进制
void toRadix(int a,int radix,char *ans) {
//边界
if(a == 0){
ans[0] = '0';
ans[1] = '\0';
return;
}
if(a < 0||radix < 1)return; //error
int num = a, index = 0;
while(num > 0) {
ans[index++] = num % radix + '0';
num = num / radix;
}
ans[index] = '\0';
reverse(ans,ans+strlen(ans)); //std
}
//radix转十进制
int toDec(char *s,int radix) {
int index = 0, ans = 0;
for(int i = strlen(s)-1;i >= 0;i--, index++){
ans += (s[i]-'0')*pow(radix,index);
}
return ans;
}
//不进位加法
void addX(char *s1, char *s2, int radix,char *ans){
int indexa = strlen(s1)-1;
int indexb = strlen(s2)-1;
int index = max(indexa,indexb);
ans[index+1] = '\0';
while(indexa>=0 && indexb>=0){
ans[index--] = (s1[indexa--]+s2[indexb--]-'0') % radix + '0';
}
while(indexa>=0)ans[index--] = s1[indexa--];
while(indexb>=0)ans[index--] = s2[indexb--];
}
int main(){
int a[10] = {2,2,2,3,3,3,8,8,8,7};
int radix = 3;
char pre[32]; //局部变量不能用char *ans
toRadix(a[0],radix,pre);
for(int i = 1;i < sizeof(a)/4;i++){
char next[32], ans[32];
toRadix(a[i],radix,next);
addX(pre,next,radix,ans);
strcpy(pre,ans);
}
printf("%d",toDec(pre,radix));
return 0;
}
public class Main {
public static void main(String[] args) {
int[] arr = {2, 2, 2, 9, 7, 7, 7, 3, 3, 3, 6, 6, 6, 0, 0, 0};
int n = arr.length;
char[][] kRadix = new char[n][];
int k = 3; //转化k进制字符数组
int maxLen = 0;
for (int i = 0; i < n; i++) {
kRadix[i] = new StringBuilder(Integer.toString(arr[i],k))
.reverse().toString().toCharArray();
if (kRadix[i].length > maxLen) {
maxLen = kRadix[i].length;
}
}
int[] resArr = new int[maxLen];
for (int i = 0; i < n; i++) {
for (int j = 0; j < maxLen; j++) { // 不进位加法
if (j >= kRadix[i].length) {
resArr[j] += 0;
} else {
resArr[j] += (kRadix[i][j] - '0');
}
}
}
int res = 0;
for (int i = 0; i < maxLen; i++) {
res += (resArr[i] % k) * (int) (Math.pow(k, i));
}
System.out.println(res);
}
}
递归
找重复：找更小规模的子问题 ①找到一种划分方法 ②找递推公式或等价转换
找变化：变化的量作为参数
找边界：出口
阶乘
//阶乘
int f(int n){
if(n == 0)return 1;
return n*f(n-1);
}
时间复杂度：O(n)
T(n) = T(n-1) + O(1) , 递归下降N层，每层O(1)
数组求和
int f(int *arr,int begin){
if(begin == arr.length()-1){
return arr[begin];
}
return arr[begin]+f(arr,begin+1);
}
字符串翻转
String reverse(String str,int end){
if(end == 0){
return ""+str.charAt(0);
}
return str.charAt(end)+reverse(str,end-1);
}
欧几里得/辗转相除法
//辗转相除法求最大公约数
int gcd(int m,int n){
if(m <= 0||n <= 0)return 0; //error
if(m % n==0)return n;
return gcd(n,m%n);
}
时间复杂度:O(lgn)
(m,n)
↓
(n,m%n) m%n < m%(m/2+1) < m/2
↓
(m%n,n%(m%n)) n%(m%n) < n/2
每下降两次，n降为一半
2次 n/2
4次 n/2^2
6次 n/2^3
k次 n/2^(k/2)
当 n/2^(k/2)=1 即 k=2lgn
汉诺塔
ABC三个柱子，小盘必须在大盘上面，初始都在A柱，从上往下编号为 1 到 N
空柱：柱上没有盘 / 要移动的盘都比柱上原有的盘小
最小子问题：
如图，将一根柱子(A)上的大小盘通过两根空柱(B,C)移动到其中一个空柱(B或C)上是可行的
小盘→C，大盘→B，小盘→B
—|— | |
——|—— | |
A B C
类推：小盘(1到N-1)→C，大盘(N)→B，小盘(1到N-1)→B
小盘(1到N-1)→C：位于A，通过两根空柱BC，从A移动到C
小盘(1到N-1)→B：位于C，通过两根“空柱”AB，从C移动到B
void hanoiTower(int N,string from,string help,string to){
if(N == 1){ //只有一个盘
cout << "move " << N << " from " << from << " to " << to << endl;
return;
}
hanoiTower(N-1,from,to,help);
cout << "move " << N << " from " << from << " to " << to << endl;
hanoiTower(N-1,help,from,to);
}
时间复杂度: O(2^n)
T(n)=2T(n-1)+O(1) //O(2^n)，(n到达27，运行时间就接近1s)
树高n，每层O(1)*2^i个节点
一共(2^0+2^1+2^2+ ... + 2^n-1) * O(1) = O(2^n) （等比数列求和）
树高为h的完全二叉树有2^h个节点
求a的n次幂
//O(n)往下降就是O(lgn)
int pow(int a,int n){
if(a == 0)return 0;
if(n == 0)return 1; //边界
int ans = a;
int ex = 1;
while( (ex<<1) <= n ){
ans = ans * ans;
ex = ex<<1;
}
return ans*pow(a,n-ex);
}
递推
斐波那契
T(n)=T(n-1)+T(n-2)+O(1); //近似为汉诺塔:T(n)=2T(n-1)+O(1)
同理:T(n)=K*T(n-1)+O(1):O(K^n)
时间复杂度:O(2^n)
上楼梯
楼梯有n阶，一次可以上1阶，2阶，3阶。计算有多少种走完楼梯的方式
f(n) = f(n-1) + f(n-2) + f(n-3);
出口：f(1) = 1; f(2) = 2; f(3) = 4;
时间复杂度:O(3^n)
最长递增子序列
//f[n]表示以a[n]为末尾的最长递增子序列长度
f[n] = max{ f[i] + 1 && a[i] < a[n], 1} (i=0,1,2...n-1)
//最长不下降子序列
f[n] = max{ f[i] + 1 && a[i] <= a[n], 1} (i=0,1,2...n-1)
最长连续递增子序列
1,9,2,5,7,3,4,6,8,0 的最长递增子序列 3,4,6,8
//方案1:
双指针,左指针固定,右指针移动,结算后左指针右移一个位置
//方案2:
f[n] = a[n]>a[n-1] ? f[n-1] + 1 : 1;
查找与排序
比较排序
冒泡排序
重复地走访过要排序的数列，越大的元素会经由交换慢慢沉下去
for(int i = 0;i < a.length;i ++){
for(int j = 0;j < a.length-1-i;j ++){
if(a[j+1] < a[j]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
性能分析：最佳：O(n) 最坏：O(n^2)
选择排序
从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾
for(int i = 0;i < a.length;i ++){
int minIndex = i;
for(int j = i;j < a.length;j ++){
if(a[j] < a[minIndex]){
minIndex = j;
}
}
if(minIndex != i){
int temp = a[minIndex];
a[minIndex] = a[i];
a[i] = temp;
}
}
性能分析：最佳：O(n^2) 最坏：O(n^2)
不稳定排序： 序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了
插入排序
将一个记录插入到已排好序的序列中。
待排第i个元素时，前面i-1个元素是有序的，从后往前扫描插入
for(int i = 0;i < a.length();i ++){
int current = a[i];
int preIndex = i-1;
while( preIndex>=0 && current<a[preIndex] ){
a[preIndex+1] = a[preIndex];
preIndex --;
}
a[preIndex+1] = current;
}
//递归写法
//对数组 0~倒数第一个元素排序 = 对数组0~倒数第二个元素排序，然后把最后一个元素插入到有序部分
void insertSort(int *a,int k){
if(k == 0)return;
insertSort(a,k-1);
int current = a[k];
int preIndex = k-1;
while( preIndex>=0 && current<a[preIndex]){
a[preIndex+1] = a[preIndex];
preIndex --;
}
a[preIndex+1] = current;
}
性能分析：最佳：O(n) 最坏：O(n^2)，在序列基本有序时很快
希尔排序
插入排序的一种。增量用于分组，组内进行插入排序。
如 9 8 7 6 5 4 3 2 1，增量为4，则 分组为（9，5，1）（8，4）（7，3）（6，2）
排序后为：1 4 3 2 5 8 7 6 9。然后缩小增量为2
//增量不断缩小
for(int interval = a.length()/2;interval >= 1;interval /= 2){
//增量为1的插入排序
for(int i = interval;i < a.length();i ++){ //自增1:各组同时更新
int current = a[i];
int preIndex = i - interval;
while(preIndex>=0 && current<a[preIndex]){
a[preIndex+interval] = a[preIndex];
preIndex-=interval;
}
a[preIndex+interval] = current;
}
}
性能分析
约为O(n^1.3)
最坏：1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16 【增量为4和2的时候均有序，增量为1时O(n^2)，增量到达1以前的增量比较均浪费，总> O(n^2) 】
最好：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 【每层约n次比较，共lgn层，总O(nlgn) 】
快速排序
注重子问题划分：小于x的元素放在左侧， 大于x的元素放在右侧
quicksqort(A,p,r)
if p<r
q = Partion(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)空间复杂度：O(lgn) 每一层要把主元缓存一下
划分方法
单向扫描法
主元 scanner bigger
↓ ↓ ↓
9 3 4 8 7 10 ... 12 9
scanner<=主元:scanner右移
scanner>主元:scanner和bigger元素交换,bigger左移
边界：如果最后一个扫描的元素大于主元，bigger左移之后小于scanner
如果最后一个扫描的元素小于等于主元,scanner右移大于bigger
int partition(int a[],int p,int r){
int pivot = a[p];
int sc = p + 1;
int bigger = r;
while(sc<=bigger){
if(a[sc]<=pivot){
sc++;
continue;
}
else{
swap(sc,bigger);
bigger --;
}
}
swap(p,bigger);
return bigger;
}
void quicksort(int a[],int p,int r){
if(p < r){
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
双向指针扫描
主元 left right
↓ ↓ ↓
x <= <= <= > ... <= > >
left一直扫描到第一个>主元的元素，right一直扫描到第一个<=主元的元素,然后交换。重复上诉流程。
边界条件
left right right left
↓ ↓ → ↓ ↓
<= <= > <= <= >
left right right left
↓ ↓ → ↓ ↓
<= > > <= > >
int partition(int a[],int p,int r){
int pivot = a[p];
int left = p + 1;
int right = r;
while(left<=right){
while(left <= right && a[left] <= pivot)left++;
while(left <= right && a[right] > pivot)right--;
if(left < right)swap(left,right);
}
swap(p,right);
return right;
}
三指针分区法
元素重复几率高
主元 sc/e bigger
↓ ↓ ↓
x < < < = < ... < = > >
e指向等于区间的首部
bigger右侧均大于主元
小于主元:a[sc]和a[e]进行交换,sc++,e++ (相当于等于区间首部右移)
主元 e sc bigger
↓ ↓ ↓ ↓
x < < < = < ... < = > >
等于主元:sc++
大于主元:a[s]和a[bigger]交换,bigger--
边界：参考一遍扫描,bigger最后一定指向等于区间的尾部
循环停止后:e--,swap(p,e);
函数返回两个位置:e,bigger分别指向等于区间的首尾部
quicksort(p,e-1)
quicksort(bigger+1,r)
优化
快排性能：O(nlgn)
但如果主元不是中位数，特别地如果每次主元都在数组区间的一侧，复杂度将退化为O(n^2)
三点中值法
//在p，r，mid中选一个中间值
int midIndex;
int mid = p+((r-p)>>1);
//if(a[mid]>=min(a[p],a[r])&&a[mid]<=max(a[p],a[r]))midIndex = p;
//else if(a[p]>=min(a[mid],a[r])&&a[p]<=max(a[mid],a[r]))midIndex = p;
//else midIndex = r;
if(a[mid]<=a[p]&&a[p]<=a[r] || a[r]<=a[p]&&a[p]<=a[mid])midIndex = p;
else if(a[p]<=a[mid]&&a[mid]<=a[r] || a[r]<=a[mid]&&a[mid]<=a[p])midIndex = mid;
else midIndex = r;
swap(midIndex,p);
int privot = a[p];
绝对中值法
保证主元在中间，即nlgn，但是常数因子会变大
每5个元素为一组(最后一组可能不足5个)，每组进行插入排序，取出每组中间值，对取出的中间值(N/5)，再做一次插入排序，再取中间值
int getMedian(int a[],int p,int r){
int size = p - r + 1;
int groupSize = (size%5==0) ? (size/5) : (size/5+1);
int *medians = new int[groupSize]; //vector<int> medians;
for(int j = 0;j < groupSize;j ++){
//单独处理最后一组
if(j == groupSize - 1){
insertSort(a,j*5,r);
medians[j] = a[(p+j*5+r)/2];
}else{
insertSort(a,j*5,j*5+4);
medians[j] = a[p+j*5+2];
}
}
insertSort(medians,0,groupSize-1);
return medians[groupSize/2];
}
小数据量用插入排序
待排序元素较少时直接用插入排序
插入排序O(n²)：并非真正的n²，而是 n(n-1)/2
快排O(nlgn)：实际上是 n(lgn+1)
n <= 8 时， n(n-1)/2 < n(lgn+1)
void quicksort(int a[],int p,int r){
if(p<r){
if(p-r+1<=8){
insertSort(a,p,r);
}
else {
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
}
归并排序
注重子问题合并：左有序，右有序，加起来合并成新的有序(借助辅助空间)
空间复杂度:O(n)
//这里辅助数组应该开在全局
void merge(int a[],int p,int mid,int r){
int *helper = new int[r-p+1]; //只new出部分空间
//0(newP) mid-p(newMid) r-p(newR)
copy(a+p,a+r+1,helper); //STL,copy(begin(a),end(a),begin(b))
int left = 0;
int right = mid-p+1;
int current = p;
while(left<=mid-p && right<=r-p){
if(helper[left] <= helper[right]){
a[current++] = helper[left++];
}else{
a[current++] = helper[right++];
}
}
while(left<=mid-p)a[current++] = helper[left++];
//右指针没到头无所谓，元素处于原来的位置上
delete(helper);
}
void mergeSort(int a[],int p,int r){
if(p < r){
int mid = p + ((r-p)>>1);
mergeSort(a,p,mid);
mergeSort(a,mid+1,r);
merge(a,p,mid,r);
}
}
堆排序
数组存储二叉树：节点 i 的左子节点2i+1，右节点 2i+2 , 父节点 (i-1)/2
o0
o1 o2
o3 o4 o5 o6
o7 o8
若数组以a[0]开始，len为数组的长度，
则最后一个叶节点的父节点：((len-1)-1)/2 = len/2-1，即最后一个非叶节点：len/2-1
适用：海量数据流
//先序遍历：根左右，中序遍历：左根右， 后序遍历： 左右根
void preOrder(int a[],int len,int i){
if(i >= len)return; //边界
cout << a[i] << endl;
preOrder(a,len,2*i+1);
preOrder(a,len,2*i+2);
}
二叉大顶堆：父节点>=子节点，每个节点的左右子树都是大顶堆
堆排序(小根堆)步骤：
1.将初始数组调整为小根堆
2.输出堆顶元素(当前最小值)，然后把堆顶和最末元素对调，更新堆大小，再调整堆顶元素
//调用函数前提:a是"类小根堆",即根节点i的左右子树都是小根堆
//调用函数效果:将根元素下沉,使a变为真正的小根堆
void Minheapfixdown(int a[],int i,int len){
if(i >= len)return; //error
int left = 2*i+1;
int right = 2*i+2;
int minIndex; //较小节点的索引
//出口:该节点没有子节点
if(left >= len)return;
//找到较小节点
if(right >= len){ //没有右节点
minIndex = left;
} else {
if(a[left]<=a[right])minIndex = left;
else minIndex = right;
}
//和根节点比较,若不小于根节点则不用调整
if(a[minIndex]>=a[i])return;
else {
swap(a,minIndex,i);
Minheapfixdown(a,minIndex,len); //根节点继续下沉
}
}
//构建小根堆
void Minheap(int a[],int len){
//从最后一个非叶节点开始依次向上调整，如图即:o3→o2→o1
// o0
// o1 o2
// o3 o4 o5 o6
// o7 o8
for(int i = len/2-1;i >= 0;i --){
Minheapfixdown(a,i,len);
}
//保证每次调整时，以i为根节点的左右子树均为小根堆，且只有根元素a[i]进行“下沉”
}
void heapsort(int a[],int len){
//先以原数组构建小根堆
Minheap(a,len);
//遍历
for(int i = len-1;i >= 0;i --){
cout << a[0] << endl; //输出最小值
swap(a,0,i); //将堆顶与最后一个节点进行对调
Minheapfixdown(a,0,i-1); //缩小堆的范围，堆顶元素下沉
}
//排序后的a为降序
}
时间复杂度：O(nlogn)
建堆：n/2 * logn (2^h-1=n)
排序：n * logn
缺点：常数因子较大 优点：排序过程颗粒化
非比较排序
计数排序
用辅助数组对数组中出现的数字计数，元素转下标，小标转元素
优点：快，缺点：若原始数据范围大，比较稀疏，会导致辅助空间浪费
适用：小规模数据，已知边界且较小，如人的年龄
空间复杂度：O(k)
void cntsort(int a[],int len){
int minNum = a[0];
int maxNum = a[0];
for(int i = 1;i < len;i ++){
if(a[i]>maxNum) maxNum = a[i];
if(a[i]<minNum) minNum = a[i];
}
int *helper = new int[maxNum-minNum+1](); //加上()动态数组初始化为0
for(int i = 0;i < len;i ++)helper[a[i]-minNum]++;
int current = 0;
for(int i = 0;i < maxNum-minNum+1;i ++){
while(helper[i]>0){ //重复元素
a[current++] = i+minNum;
helper[i] --;
}
}
}
桶排序
设计k个桶(0~k-1)，将n个输入分布到各桶中，在各桶内排序，然后按次序列出各桶中的元素(搜集)
一种入桶算法：value*n/(max+1)，结果在区间[0,n-1]（即n个桶的编号）
适用：分布均匀的数据
//c++(vector实现)
void bucketSort(int a[],int len,int bucketSize){
//注意数组在传递过程中,sizeof(a)返回的实际是指针的大小8
//所以在传参的时候正确的做法是要加上数组的len
//1.获取待排序列中的最小值min和最大值max
int maxNum = a[0];
int minNum = a[0];
for(int i = 0;i < len;i ++){
if(a[i]>maxNum) maxNum = a[i];
if(a[i]<minNum) minNum = a[i];
}
//2.根据max和min的差值范围以及每个桶的大小，确定桶的个数
int bucketCount = (maxNum-minNum)/bucketSize + 1;
vector<int> buckets[bucketCount];
//3.遍历待排序序列，将每个元素放入相对应的桶中
for(int i = 0;i < len;i ++){
buckets[(a[i]-minNum)/bucketSize].push_back(a[i]);//注意insert(iterator,val)
}
//4.对每个桶中的元素进行排序,并输出
int k = 0;
for(int i = 0;i < bucketCount;i ++){
sort(buckets[i].begin(),buckets[i].end());
for(int j = 0;j < buckets[i].size();j ++){
a[k ++] = buckets[i][j];
}
}
}
//c链表实现(待完成)(hash)
//下面是别人的参考写法
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int key;
struct node* next;
}KeyNode;
void bucket_sort(int keys[],int size,int bucket_size);
int main()
{
int a[]={11,11,9,21,14,55,77,99,53,25};
int size=sizeof(a)/sizeof(a[0]);
bucket_sort(a,size,10);
return 0;
}
void bucket_sort(int keys[],int size,int bucket_size)
{
KeyNode **bucket_table=(KeyNode**)malloc(bucket_size*sizeof(KeyNode*));
for(int i=0;i<bucket_size;i++){ //初始化桶
bucket_table[i]=(KeyNode*)malloc(sizeof(KeyNode));
bucket_table[i]->key=0;
bucket_table[i]->next=NULL;
}
for(int i=0;i<size;i++){
KeyNode* node=(KeyNode*)malloc(sizeof(KeyNode));
node->key=keys[i];
node->next=NULL;
int index=keys[i]/10;//给数据分类的方法（关系到排序速度，很重要）
KeyNode *p=bucket_table[index];
if(p->key==0){
p->next=node;
p->key++;
}
else{
while(p->next!=NULL&&p->next->key<=node->key){//=的时候后来的元素会排在后面
p=p->next;
}
node->next=p->next;
p->next=node;
(bucket_table[index]->key)++;
}
}
KeyNode* k=NULL;
for(int i=0;i<bucket_size;i++){
for(k=bucket_table[i]->next;k!=NULL;k=k->next){
printf("%d ",k->key);
}
}
}
性能分析
最好：分布均匀(即每个元素独占一个桶)，出桶和入桶都是O(n)
最坏：都进入一个桶中，O(nlogn) (假设桶内快排)
假设分布均匀：k=N/M， O(N+klgk) = O(N+NlgN-NlgM) = O(N+C) (M个桶)
空间复杂度：O(n+k)，动态数组，需要n个位置，k个桶
基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位
适用：整数数值型排序
vector<int> bucket[10]; //vector放全局变量减少每次初始化消耗
int getNumD(int x,int d){
// char tmp[MAXLEN];
// sprintf(tmp,"%d",&d);
// return tmp[strlen(tmp)-d]-'0';
while(d --){
x = x / 10;
if(d == 0)return x % 10;
}
}
//对数组a按第d位来进行排序和搜集
void dsort(int a[],int len,int d){
//入桶
for(int i = 0;i < len;i ++){
int index = getNumD(a[i],d);
bucket[index].push_back(a[i]);
}
//排序
for(int i = 0;i < 10;i ++){
sort(bucket[i].begin(),bucket[i].end());
}
//搜集
int k = 0;
for(int i = 0;i < 10;i ++){
for(int j = 0;j < bucket[i].size();j ++){
a[k ++] = bucket[i][j];
}
bucket[i].clear();
}
}
void radixSort(int a[],int len){
int dnum = 0; //maxNum的位数
int *maxNum = max_element(a,a+len); //STL
//若有负数和0,可全部先转化为正数
//if(*maxNum == 0)....
while(*maxNum > 0){
dnum ++;
*maxNum /= 10;
}
int k = 1;
while(k <= dnum){
dsort(a,len,k++);
}
}
性能分析
时间复杂度O(kn) ， 空间复杂度O(n+k)， 这里的k为10
例题
调整数组顺序使奇数位于偶数前面
要求在O(n)时间范围内完成
//归并排序的思想:开n大小的辅助空间
void adjust(int a[],int len){
int *helper = new int[len];
copy(a,a+len,helper);
int current = 0;
int left = 0;
int right = len-1;
while(current<len){
if(helper[left]%2)a[left++] = helper[current++];
else a[right--] = helper[current++];
}
}
//快排的思想
void adjust(int a[]){
int sc = 0;
int odd = len-1;
while(sc <= odd){
if(a[sc]%2){
sc++;
} else {
swap(sc,odd);
odd--;
}
}
}
乱序数组第k大元素
//方案1:先快排,再抽取 nlgn
//方案2:参考快排的分区算法(限制:需要改动数组内容)
int select(int a[],int p,int r,int k){
q = partition(a,p,r); //a[p...q-1]<=a[q](主元)<=a[q+1...r]
qk = q - p + 1; //主元是第qk大元素
if(qk == k)return a[q];
else if(qk > k)return select(a,p,q-1,k);
else return select(a,q+1,r,k-qk); //注意k-pk
}
//返回a[p...r]中第k大的元素t,同时保证改动后a[p...p+k-2]<=t<=a[p+k...r]
方案2性能分析:
最坏: 每次分区只丢掉了一个数字. 如查询1 2 3 4 5 中第5大的元素
第一次分区: 以1为主元, 比较了4次, 递归在子分区 2 3 4 5 中找第4大的元素
第二次分区: 以2为主元, 比较了3次, 递归在子分区 3 4 5 中找第3大的元素 ...
1 + 2 + 3 + 4 → 1 + 2 + 3 + ... + n = n(n+1)/2 → O(n^2)
最好: 每次分区主元都选到了中位数 (三点定中法)
o ---- n
↘
o ----- n/2
↘
o ----- n/4
n(1 + 1/2 + 1/4 + 1/8 + .... ) = 2n → O(n)
1 + x^2 + x^3 + x^4 + ... = 1/1-x (x < 1) //几何级数
找出数组中出现次数超过一半的数字
2 8 1 8 4 8 8 , 返回8
顺序统计的第n/2个肯定是超过一半的数字
//方案1,排序后返回a[n/2]
//方案2,参考乱序数组第k大元素(需要改动数组内容)
//方案3,消除法(不改动数组内容),利用出现次数超过一半
int number = 0; //记录数字
int cnt = 0; //记录次数
for(int i = 0;i < a.length;i ++){
if(cnt == 0){
number = a[i];
cnt ++;
} else {
if(a[i] != number)cnt --;
else cnt ++;
}
}
return number;
2 8 1 8 4 8 8 8
2:2 1
8:2 0 //2和8数字不同
1:1 1 //重置
8:1 0 //1和8数字不同
4:4 1 //重置
8:4 0 //4和8数字不同
8:8 1 //重置
8:8 2 //出现次数加
若"水王"刚好出现一半
//1.水王占总数一半,说明总数为偶数
//2.若最后一个数不是水王,去掉最后一个数,两两消减结果为水王.水王和最后一个数相消,但number不变
//3.若最后一个数是水王,新增计数器统计最后一个数出现的次数,若为N/2即是水王
int number = 0; //记录数字
int cnt = 0; //记录次数
int same = 0;
for(int i = 0;i < N;i ++){
if(a[i] == a[N-1])same ++;
if(cnt == 0){
number = a[i];
cnt ++;
} else {
if(a[i] != number)cnt --;
else cnt ++;
}
}
if(same == N/2)return a[N-1];
else return number;
最小可用ID
在乱序非负数组中找到最小可分配的id(从1开始编号), 1000000
3 2 1 4 5 8 9 6 7 11 ... 后面都没出现10, 那么最小可用的id是10
1 2 3 4 5 ... n n+1 没有缺席的,那么最小可用的id是n+2
//方案1:从1开始探测每个自然数是否在数组中 O(n^2)
//方案2:先排序,再顺序探测不在其位的自然数: i+1 != a[i] O(nlgn)
//方案3:开辅助空间填空,再顺序扫描 O(n)
//方案4:快排分区
//返回a[p...r]中第k大的元素t,同时保证改动后a[p...p+k-2]<=t<=a[p+k...r]
int selectK(int a[],int p,int r,int k){
q = partition(a,p,r);
qk = p - q + 1;
if(qk == k)return a[q];
else if(qk > k)return selectK(a,p,q-1,k);
else return selectK(a,q+1,r,k-qk)
}
int find(int a[],int p,int r){
if(p > r)return p+1; //出口
int mid = p + ((r-p)>>1);
int t = selectK(a,p,r,mid-p+1);
/* 3 1 4 5, p = 0, r = 3, mid = 1, mid-p+1 = 2
* 返回的t为数组中第2大的元素3,且保证数组变为:x1 t x2 x3 (x1<=t<=x2,x3)
* 即: 1 3 4 5 或 1 3 5 4
* 因为 第2大的元素3大于期望值2, 说明缺失发生在3的左侧
*/
if(t == mid + 1){ //缺失值在右侧
return find(a,mid+1,r);
} else { //缺失值在左侧
return find(a,p,mid-1);
}
}
//出口
1 2 4 5 6
p=0,r=4,mid=2;找到数组[1,2,4,5,6]中第mid-p+1=3大的元素4,发现左侧缺失,调用find(a,0,1);
p=0,r=1,mid=0;找到数组[1,2]中第1大的元素1,发现左侧紧密,调用find(a,1,1);
p=1,r=1,mid=1;找到数组[2]中第1大的元素2,满足,在右侧找缺失值,调用find(a,2,1);
满足出口条件,返回3
合并有序数组
给定排序后的数组A和B,A的末端有足够的缓冲空间容纳B.合并两数组
//归并的思想
void merge(int a[],int b[],int lena,int lenb){
int current = lena+lenb-1;
int indexA = lena-1;
int indexB = lenb-1;
while(indexA>=0&&indexB>=0){
if(a[indexA]>b[indexB]){
a[current--] = a[indexA--];
} else {
a[current--] = b[indexB--];
}
}
while(indexB>=0)a[current--] = b[indexB--];
}
数列中逆序对个数
//方案1：dp[n] = dp[k] + 1 (a[n]>a[k],a[n]<a[n-1...k+1]) n^2
//方案2：nlgn，归并
int cnt;//逆序对计数器
void merge(int a[],int p,int mid,int r){
int *helper = new int[r-p+1]; //只new出部分空间
//0(newP) mid-p(newMid) r-p(newR)
copy(a+p,a+r+1,helper); //STL,copy(begin(a),end(a),begin(b))
int left = 0;
int right = mid-p+1;
int current = p;
//a[p...mid],a[mid+1...r]均已排好序，进行合并时统计逆序对个数
//例:6 7 8/3 5 10, 取出右侧3，逆序对个数+=左侧剩余元素个数3 ...
//取出右侧10，逆序对个数+=左侧剩余元素个数0
while(left<=mid-p && right<=r-p){
if(helper[left] <= helper[right]){
a[current++] = helper[left++];
}else{
a[current++] = helper[right++];
cnt += (mid-p)-left+1;
}
}
while(left<=mid-p)a[current++] = helper[left++];
//右指针没到头无所谓，元素处于原来的位置上
delete(helper);
}
void mergeSort(int a[],int p,int r){
if(p < r){
int mid = p + ((r-p)>>1);
mergeSort(a,p,mid);
mergeSort(a,mid+1,r);
merge(a,p,mid,r);
}
}
排序数组中找和的因子
给定已排序数组a和k，不重复打印a中所有相加和为k的不降序二元组
如a={-8，-4，-3，0，2，4，5，8，9，10}，打印(0，10)（2，8）
//方案1： nlogn（二分查找）
//方案2：双指针
int left = 0;
int right = len-1;
while(left < right){
if(a[left]+a[right]==k){
cout << a[left] << " " << a[right] << endl;
left++;
}
else if(a[left]+a[right]<k)left ++;
else right--;
}
//拓展：三元组
for(int i = 0;i < len-2;i ++){
int left = i+1;
int right = len-1;
int ki = k - a[i];
while(left < right){
if(a[left]+a[right]==ki){
cout << a[left] << " " << a[right] << endl;
left++;
}
else if(a[left]+a[right]<ki)left ++;
else right--;
}
}
需要排序的子数组
给定一个无序数组a，求出需要排序的最短子数组长度，要求O(N)
如a={2，3，7，5，4，6}，返回4，因为只有{7，5，4，6}需要排序
//1.实现排序后为升序的情况
int left = -1; //需要排序的最短子数组的左端点
int right = -1;
int max = a[0]; //历史最高点
int min = a[len-1]; //历史最低点
for(int i = 0;i < len;i ++){
if(a[i]>max)max = a[i]; //更新历史最高点
if(a[i]<max)right = i; //只要低于历史最高点就要拓展排序区间的右端点
}
for(int i = len-1;i >= 0;i --){
if(a[i]<min)min = a[i]; //更新历史最低点
if(a[i]>min)left = i; //只要高于历史最低点就要拓展排序区间的左端点
}
if(left == -1)return 0;
int tmp1 = right-left+1;
//2.实现排序后为降低序的情况
//TODO...
int tmp2 = right-left+1;
return tmp1<tmp2?tmp1:tmp2;
前k个数
求海量正整数按逆序排列的前k个数(topK)。因为数据量太大不能全部存储在内存中，只能一个个从磁盘或网络上读取数据，设计高效算法解决问题。注意：第一行输入k，后N行不限制用户输入数据个数，用户每输入一个数据就回车使得程序可立即获得这个数据，用户输入-1代表终止，输出topk由小到大
//O(NK)
维护一个k区间长度的缓冲区，每读入一个数，与缓冲区内最小数做比较和交换
//O(Nlogk)
维护一个小顶堆，每读入一个数，和堆顶做比较和向下调整
数组能排成的最小数（特殊排序）
输入一个正整数数组，把数组里所有整数拼接起来排成一个数，打印出能拼接出的所有数字中最小的一个。如{3，32，321}，打印321323
排序的比较方式发生改变：
b<a: ba < ab (这里的ba指的是数字串b拼接到a前面)，即b串排在前面的优先级更高
基于上述比较方式进行从小到大排序再依次拼接
private static int f(Integer[] a){
//基于快排+插入排序
Arrays.sort(a, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
String s1 = o1 + "" + o2;
String s2 = o2 + "" + o2;
return s1.compareTo(s2);
}
});
StringBuilder sb = new StringBuilder();
for(int i = 0;i < a.length;i ++){
sb.append(a[i]);
}
return Integer.parseInt(sb.toString());
}
int compare(int a,int b){
string o1,o2;
stringstream ss;
ss << a;
ss >> o1;
ss.clear();
ss << b;
ss >> o2;
ss.clear();
if(o1 == o2) return 0;
return (o1+o2)<(o2+o1) ? -1:1;
}
sort(a,a+len,cmp);
+++
查找
二分查找
int binarySearch(int *a,int target,int low,int up){
while(low <= up){
int mid = low + ((up-low)>>1); //防溢出+高效
if(a[mid]<target)up = mid - 1;
else if(a[mid]>target)low = mid + 1;
else return mid;
}
return -1;
}
//递归写法
int binarySearch(int *a,int target,int low,int up){
if(low > up)return -1;
int mid = low + (up-low)>>1;
if(a[mid]<target)return binarySearch(a,target,low,mid-1);
else if(a[mid]>target)return binarySearch(a,target,mid+1,up);
else return mid;
}
例题
数组的包含
输入两个字符串str1和str2，判断str1中的所有字符是否都存在于str2中
排序后用二分查找
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素
如：{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1
int minNum(int a[],int len){
int begin = 0, end = len-1;
if(a[begin]<a[end])return a[begin]; //没有发生旋转的情况
if(a[begin]==a[end]){ //重复数字:1 1 1 0 1
//顺序查找最小值并返回
}
//1 2:前面已经退出
//2 1
//2 3 1
//3 1 2
//3 4 5 1 2
//4 5 1 2 3
//边界是只剩两个数的时候
while(end-begin+1>2){
int mid = begin + ((end-begin)>>1);
if(a[begin] < a[mid])begin = mid; //左边有序,在右边找
else if(a[begin] > a[mid])end = mid; //左边无序,在左边找
else{ //1 0 1 1 1
//顺序查找最小值并返回
}
}
return a[end]; //最小值一定为右值
}
在有空串的有序字符串数组中查找
有个排序后的字符串数组，其中散布着一些空串，找出给定字符串的索引
如 a "" ac "" ad b "" ba , 查找b返回5
int work(){
string a[] = {"a","" ,"ac","","ad","b","","ba"};
//string a[] = {"a","" ,"b","","","","",""};
//string a[] = {"","","","","","a","" ,"b"};
string target = "b";
int begin = 0;
int end = sizeof(a)/sizeof(a[0])-1;
while(begin <= end){
int mid = begin + ((end - begin)>>1);
if(a[mid] == ""){
//找到mid右侧第一个非空串
while(a[mid] == "" && mid <= end)mid ++;
//若初始mid的右侧均为空串
if(mid == end+1){
end = begin + ((end - begin)>>1);
continue;
}
}
if(a[mid]<target)begin = mid+1;
else if(a[mid]>target)end = mid-1;
else return mid;
}
return -1;
}