基础算法1
排序
快排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void quick_sort(int a[],int begin,int end){
if(begin >= end) return ;
int i = begin - 1, j = end + 1, mid = a[ begin + end >> 1];
while(i<j){
do i++;while(a[i]<mid);
do j--;while(a[j]>mid);
if(i < j) swap(a[i],a[j]);
}
quick_sort(a,begin,j);
quick_sort(a,j+1,end);
}
|
归并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void merge_sort(int a[], int begin,int end){
if(begin >= end) return ;
int mid= begin + end >> 1;
merge_sort(a,begin,mid);
merge_sort(a,mid+1,end);
int k=0,i=begin,j=mid+1;
while( i<=mid && j<=end )
if(a[i]<=a[j]) tmp[k++]=a[i++];
else tmp[k++]=a[j++];
while(j<=end) tmp[k++]=a[j++];
while(i<=mid) tmp[k++]=a[i++];
for(i=begin,j=0;i<=end;j++,i++) a[i]=tmp[j];
}
|
二分
整数二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int bsearch1(int a[],int l,int r){
while(l<r){
int mid= l+r+1 >> 1;
if(check(mid)) l=mid;
else r=mid-1;
}
return l;
}
int bsearch2(int a[],int l,int r){
while(l<r){
int mid= l+r >> 1;
if(check(mid)) r=mid;
else l=mid+1;
}
return l;
}
|
数的范围：给定义一个有序数组，求出输入的数的起始下标和终止下标 若不存在则返回-1 -1。输入格式：先输入两个数，表示数组长度m和数组中被查找的元素的数目n，第二行输入数组各元素 共m个，后续的n行输入具体的被查找的元素的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <stdio.h>
using namespace std;
const int N=100000;
int a[N];
int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++) scanf("%d",&a[i]);
while(n--){
int x;
cout<<endl;
scanf("%d",&x);
int l=0,r=m-1;
while(l<r){
int mid= l+r >>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]!=x) cout<<"\n-1 -1";
else
{
cout << "\n"<<l<<" ";
int l=0,r=m-1;
while(l<r){
int mid = l+r+1 >>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
cout<<l;
}
}
return 0;
}
|
浮点数二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int main(){
doub accuracy=1e-6;
double x;
cin>>x;
double l=0,r=x;
while(r-l>accuracy){
double mid= (l+r)/2;
if(mid*mid >= x) r=mid;
else l=mid;
}
cout<<l;
return 0;
}
|
习题
第K小数
输入一个序列，求这个序列的第K小数。输入：序列长度 序列各元素 K 输出：第K小数
用快排的思想可以较高效率地求出。有几个问题：
- 每一次递归时，子序列的K要不要改变，即K是全局的，还是序列局部的？
- 应该如何快速递归应该传入的参数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=100010;
int a[N];
int KthMin(int l,int r,int k){
if(l>=r) return a[l];
int i=l-1,j=r+1,mid=a[ i+j >>1];
while(i<j){
do i++; while(a[i]<mid);
do j--; while(a[j]>mid);
if(i<j) swap(a[i],a[j]);
}
int leftTotal=j-l+1;
if(leftTotal >= k) return KthMin(l,j,k);
return KthMin(j+1,r,k-leftTotal);
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
printf("%d",KthMin(0,n-1,k));
return 0;
}
|
针对上面的问题，回答是：
K是局部的，需要在子序列中相应调整， 并且要根据子序列在基准的左侧or右侧，做出不同的K值调整，结合图形分析，同样，第二个问题也是通过画图的方式来帮助分析最好。
递归时不能写成：
1
2
3
4
5
| if(leftTotal > k) return KthMin(l,j,k);
else if(leftTotal < k) return KthMin(j+1,r,k-leftTotal);
else return a[leftTotal-1];
|
逆序对数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
分治（归并排序）的思想，取区间的中点，那么这个区间的逆序对的数量应该是，左侧区间逆序对的数量+右侧逆序对的数量+跨左右的逆序对的数量，然后对每个子区间按同样的方式来求，知道区间很小，只有两个数字，可以立马得出。然后得到上一层递归的结果，进而得到最终结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int N= 100010;
int a[N];
LL reversePair(int l,int r){
if(r-l==1) return a[l]>a[r];
if(r<=l) return 0;
int mid = l + r >> 1;
int leftPair=0,rightPair=0,betweenPair=0;
leftPair=reversePair(l,mid);
rightPair=reversePair(mid+1,r);
for(int i=mid+1;i<=r;i++){
for(int leftIndex=l;leftIndex<=mid;leftIndex++){
if(a[leftIndex]>a[i]) {
betweenPair++;
}
}
}
return leftPair+rightPair+betweenPair;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
printf("%d",reversePair(0,n-1));
return 0;
}
|
改进后的代码如下：
思路：仍然是基于分治，在处理跨左右的区域的部分时，会进行排序操作，将左右两端区域都有序化（自底向上的归并排序），再数据量极大时，由于左右两侧的数据都是有序的，因此当找到一个逆序对后，就可以判断左侧剩余的数据都是逆序对，也就是一旦满足a[i]>a[j] 则可以直接求出对于此时右侧那个元素的逆序对的数量了，为：mid-i+1，然后直接复制好元素后移动右侧指针即可。精髓是：一边排序，用来方便上一层（大规模数据）的求解的同时，求出此层的逆序对数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int N= 100010;
int a[N],tmp[N];
LL reversePair(int l,int r){
if(r<=l) return 0;
int mid = l + r >> 1;
LL leftPair=0,rightPair=0,betweenPair=0;
leftPair=reversePair(l,mid);
rightPair=reversePair(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r ){
if(a[i]<=a[j]) tmp[k++]=a[i++];
else{
betweenPair += mid - i + 1;
tmp[k++]=a[j++];
}
}
while(i<=mid) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
for(i=l,j=0;i<=r;i++,j++) a[i]=tmp[j];
return leftPair+rightPair+betweenPair;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
printf("%lld",reversePair(0,n-1));
return 0;
}
|
三次方根
求一个数的三次方根
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <stdio.h>
using namespace std;
const double ACCURACY=1e-8;
int main(){
double n;
scanf("%lf",&n);
double l=-100,r=100;
while(r-l>ACCURACY){
double mid = (r+l)/2;
if(mid*mid*mid >= n) r=mid;
else l = mid;
}
printf("%.6lf",l);
}
|