算法基础-基础算法
快速排序
01.快速排序
题目描述
给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1\le n\le 100000
输入样例：
5
3 1 2 4 5输出样例：
1 2 3 4 5题解
时间复杂度:
O(nlogn)
时间复杂度图:
核心思想:
首先找到 x = q[ l +r >> 1]
如果小于x就放在x的左边 否则我们就放在x的右边 递归处理
tips: 注意边界问题
这个板子我们让 i = l - 1 , j = r + 1 就从两端开始查找 然后分左右进行递归
快排思想图:
核心函数:
void quick_sort(int* q , int l , int r ）{
if(l >= r ) return ;
int x = q[ l + r >> ] , i = l - 1 , j = r + 1 ;
while (i < j )
{
do i ++ ; while(q[i] < x) ;
do j -- ; while(q[j] > x) ;
if (i < j) swap(q[i] , q[j] ) ;
else
{
qucik_sort(q , l , j ) , qucik_sort(q , j + 1 , r ) ;
}
}
}代码实现:
Method1 - 手写快排
#include <iostream>
using namespace std ;
const int N = 1e5 + 10 ;
int n ;
int q[N] ;
void quick_sort(int* q , int l, int r) {
if (l >= r) return ;
int x = q[(l + r) / 2] , i = l - 1 , j = r + 1 ;
while (i < j)
{
do i ++ ; while (q[i] < x) ;
do j -- ; while (q[j] > x) ;
if (i < j ) swap(q[i] , q[j]) ;
}
quick_sort(q , l , j) ;
quick_sort(q , j + 1 , r) ;
}
int main () {
scanf("%d",&n) ;
for (int i = 0 ; i < n ; i++) scanf("%d" , &q[i]) ;
quick_sort(q , 0 , n - 1 ) ;
for (int i = 0 ; i < n ; i ++) cout << q[i] << " " ;
cout << endl ;
return 0 ;
}
Method2 - C++STL
#include <iostream>
#include <algorithm>
using namespace std;
int main (){
int n;
cin >> n;
int a[n];
for (int i = 0; i < n ; i ++ ) cin >> a[i];
sort(a, a + n);
for (auto x : a) cout << x << " ";
return 0;
}02.第k个数
题目描述
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n个整数（所有整数均在 1∼10^9范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 k小数。
数据范围
1\le n\le 1000001\le k\le n
输入样例：
5 3
2 4 1 5 3输出样例：
3题解
时间复杂度:
O(nlgn) 比直接快排快一倍
核心思想
总体思想与快排一致判断 在quick_sort中增加大小判断机制
核心函数
void quick_sort(int k , int l , int r ) {
if (l >= r ) return q[l] ;
int x = q[l + r >> 1 ] , i = l - 1 , r = j + 1 ;
while ( i < j )
{
do i ++ ; while (q[i] < x ) ;
do j -- ; while (q[j] > x ) ;
if (i < j ) swap(q[i] , q[j] ) ;
}
int sl = j - l + 1 ;
if (sl >= k ) return qucik_sort(k , l , j ) ;
else
return qucik_sort（k - sl , j + 1 , r ) ;
}代码实现
Method1 - 手写快排
#include <iostream>
using namespace std ;
const int N = 100010 ;
int n , k ;
int q[N] ;
int quick_sort(int l , int r , int k) {
if (l >= r) return q[l] ;
int x = q[(l + r) / 2] , i = l - 1 , j = r + 1 ;
while(i < j)
{
do i ++ ; while (q[i] < x) ;
do j -- ; while (q[j] > x) ;
if (i < j) swap (q[i] , q[j]) ;
}
int sl = j - l + 1 ;
if (k <= sl) return quick_sort(l , j , k) ;
return quick_sort(j + 1 , r , k - sl);
}
int main () {
cin >> n >> k ;
for (int i = 0 ; i < n ; i++) cin >>q[i] ;
cout << quick_sort(0 , n - 1 , k ) ;
return 0 ;
}Method2 - nth_element()
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
int main(){
cin >> n >> k;
for(int i = 0; i < n; i ++)
cin >> q[i];
nth_element(q, q + k - 1, q + n);
cout << q[k - 1] << endl;
return 0;
}归并排序
01.归并排序
题目描述
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1\le n\le 100000
输入样例：
5
3 1 2 4 5输出样例：
1 2 3 4 5题解
时间复杂度
O(nlogn)
核心思想
分一为二 合二为一 先将一个无序的序列分为两个无序的的序列 进行递归处理 然后将两个有序的序列合成为一个有序的序列
- 有数组 q, 左端点 l, 右端点 r
- 确定划分边界 mid
- 递归处理子问题 q[l..mid], q[mid+1..r]
- 合并子问题 主体合并 至少有一个小数组添加到 tmp数组中 收尾 可能存在的剩下的一个小数组的尾部直接添加到 tmp 数组中 复制回来 tmp 数组覆盖原数组
归并排序思想图:
核心函数
void merge_sort(int* q, int l, int r){
//递归的终止情况
if(l >= r)return;
//第一步：分成子问题
int mid = l + r >> 1;
//第二步：递归处理子问题
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
//第三步：合并子问题
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) temp[k ++ ] = q[i ++ ];
else temp[k ++ ] = q[j ++ ];
}
while(i <= mid) temp[k ++ ] = q[i ++ ];
while(j <= r) temp[k ++ ] = q[j ++ ];
for(i = l, j = 0; i <= r; i ++, j ++)
q[i] = temp[j];
}代码实现
#include <iostream>
using namespace std;
const int N = 100010;
int n, q[N], temp[N];
void merge_sort(int* q, int l , int r ){
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
if(q[i] <= q[j]) temp[k ++ ] = q[i ++ ];
else temp[k ++ ] = q[j ++ ];
while(i <= mid ) temp[k ++ ] = q[ i ++ ];
while(j <= r) temp[k ++ ] = q[j ++ ];
for(int i = l, j = 0; i <= r; i ++, j ++) q[i] = temp[j];
}
int main (){
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> q[i];
merge_sort(q, 0, n - 1);
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
cout << endl;
return 0;
}02.逆序对的数量
题目描述
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1\le n\le 100000,数列中的元素的取值范围 [1, 10^9]。
输入样例：
6
2 3 4 5 6 1输出样例：
5题解
时间复杂度
O(nlogn)
核心思想
求逆序对问题实际上有3种解法，分别是冒泡排序，归并排序，树状数组。
这里可以运用我们性价比最高，代码最好写，效率特高的归并排序算法
归并排序中的左数组和右数组在内部都是有序且相对原数组中的位置都是从左到右的，我们可以利用这一性质当我们判断左数组中的某一个元素(下标为i)大于右数组时, 则该元素往后的数都与右数组中的该数构成逆序对即会产生mid - i + 1个逆序对
核心代码
if(q[i] <= q[j])
temp[k ++ ] = q[i ++ ];
else
{
temp[k ++ ] = q[j ++ ];
res += mid - i + 1;
}核心函数
long long merge_sort(int l, int r){
if(l >= r)
return 0;
int mid = l + r >> 1;
long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
{
if(q[i] <= q[j])
temp[k ++ ] = q[i ++ ];
else
{
res += mid - i + 1;
temp[k ++ ] = q[j ++ ];
}
}
while(i <= mid)
temp[k ++ ] = q[i ++ ];
while(j <= r)
temp[k ++ ] = q[j ++ ];
for(int i = 0, j = l; j <= r;j ++, i ++)
q[j] = temp[i];
return res;
}代码实现
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], temp[N];
long long merge_sort(int l, int r){
if(l >= r)
return 0;
int mid = l + r >> 1;
long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
{
if(q[i] <= q[j])
temp[k ++ ] = q[i ++ ];
else
{
res += mid - i + 1;
temp[k ++ ] = q[j ++ ];
}
}
while(i <= mid)
temp[k ++ ] = q[i ++ ];
while(j <= r)
temp[k ++ ] = q[j ++ ];
for(int i = 0, j = l; j <= r;j ++, i ++)
q[j] = temp[i];
return res;
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++)
cin >> q[i];
long long res = merge_sort(0, n - 1);
cout << res << endl;
return 0;
}二分
01.数的范围
题目描述
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1\le n\le 100000
1\le q\le 100001\le k\le 10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5输出样例：
3 4
5 5
-1 -1题解
时间复杂度
O(nlogn)
单次查找是logn的
核心思想
二分的板子很简单:
int l = 0, r = n - 1; // l 和 r 分别为左端点和右端点的闭区间
while(l < r)
{
// int mid = l + r + 1 >> 1;
int mid = l + r >> 1; // 这边 l + r >> 1 还是 l + r + 1 >> 1 check函数后是不是 l = mid;
if(check(mid))
r = mid;
// l = mid;
else
l = mid + 1;
// r = mid - 1;
}
// 如果是整数二分最终得到的l和r必定相等而且满足 check(l) 且 check(r);当然本题用c++的算法库的二分查找函数 lower_bound 和upper_bound做是更快的
lower_bound(array + begin, array + end, value) - array返回begin~end之间大于等于value的第一个下标对应的位置
upper_bound(array + begin, array + end, value) - array 返回begin~end之间大于value的第一个下标对应的位置
核心函数
手写二分
while(q --)
{
int x;
cin >> x;
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] >= x) r = mid;
else
l = mid + 1;
}
if(a[l] != x)
cout << -1 << " " << -1 << endl;
else
{
cout << l << " ";
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] <= x)
l = mid;
else
r = mid - 1;
}
cout << l << endl;
}
}算法库二分
while(q --)
{
int x; cin >> x;
int l = lower_bound(a, a + n, x) - a;
if(a[l] != x)
cout << -1 << " " << -1 << endl;
else
{
cout << l << " " << upper_bound(a, a + n, x) - a - 1 << endl;
}
}代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n, q;
int main(){
cin >> n >> q;
for(int i = 0; i < n; i ++)
cin >> a[i];
while(q --)
{
int x;
cin >> x;
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] >= x)
r = mid;
else
l = mid + 1;
}
if(a[l] != x)
{
cout << -1 << " " << -1 << endl;
}
else
{
cout << l << " ";
l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] <= x)
l = mid;
else
r = mid - 1;
}
cout << r << endl;
}
}
}02.数的三次方根
题目描述
给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围
-10000 \le n \le 10000
输入样例：
1000.00输出样例：
10.000000题解
时间复杂度
O(logn)
浮点数的二分就没有临界条件需要判断直接写就可以了
核心函数
double l = -2e9, r = 2e9;
while(r - l > 1e-8)
{
double mid = (l + r) / 2.0;
if(mid * mid * mid >= x) r = mid;
else
l = mid;
}代码实现
#include <iostream>
using namespace std;
int main (){
double x;
cin >> x;
double l = -2e9, r = 2e9;
while(r - l > 1e-8)
{
double mid = (l + r) / 2.0;
if(mid * mid * mid >= x) r = mid;
else
l = mid;
}
printf("%.6lf\n", l);
return 0;
}高精度
01.高精度加法
02.高精度减法
03.高精度乘法
04.高精度除法
前缀和与差分
01.前缀和
02.子矩阵的和
03.差分
04.差分矩阵
双指针算法
01.最长连续不重复子序列
题目描述
给定一个长度为 n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0 \sim 10^5范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1 \le n \le 10^5
输入样例：
5
1 2 2 3 5输出样例：
3题解
时间复杂度
核心函数
for(int i = 0; j = 0; i < n; i ++)
{
s[a[i]] ++ ;
while(s[a[i]] > 1)
s[a[j ++ ] -- ;
res = max(res, i - j + 1);
}代码实现
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int s[N];
int main(){
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
int res = 0;
for(int i = 0, j = 0; i < n; i ++)
{
s[a[i]] ++ ;
while(s[a[i]] > 1)
s[a[j ++ ]] -- ;
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}02.数组元素的目标和
03.判断子序列
位运算
01.二进制中1的个数
离散化
01.区间和
区间合并
02.区间合并
腾讯云开发者
