《算法笔记》总结No.8——双指针
去年发表过较简单的双指针案例，建议先行阅读~
一.定义
相比说双指针是一种算法，他更倾向是一种编程技巧，话不多说直接看一个引例：
1.正整数和
如下，给定递增序列【1,3,5,7,9】，寻找到两个相加为16的元素。如果使用暴力的思想，相当于是一个双层循环：外层下标i对应的A[i]和内层下标为j的A[j]之和为16，则算一个合法的答案。
然而双层循环的复杂度为N方，当N特别大时，这显然是无法接受的。
但是仔细想一想不难发现——其实在这个暴力过程中出现了很多无用功：
- 当A[i]+A[j]＞16时，由于序列是递增的，所以A[i]+A[j+1]是必定大于16的，因此后面的查找是多余的
- 当A[i]+A[j]＞16时，还是由于递增的性质，显然也没必要比较A[i+1]+A[j]的值~
不难发现，上面两种导致多余查找的原因在于，i和j的枚举是相互牵制的，因此要想到一种可以同时考虑i和j的算法——就有了接下来双指针的思想~
令下标i的值为0，而j的值为数组的长度n-1，然后根据 A[i]+A[j]和目标值M的大小关系进行3种不同的选择，直到j>i为止：
- 如果A[i]+A[j]=M：说明找到了一种方案，此时无论是A[i+1]+A[j]>M还是A[i]+A[j-1]<M均成立，但是A[i+1]+A[j-1]与M的关系却未知，因此要i+1且j-1
- 如果A[i]+A[j]>M：此时A[i+1]+A[j]>M必然成立，因此只能移动j，j=j-1
- 如果A[i]+A[j]<M：此时A[i]+A[j-1]<M必然成立，因此只能移动i，i=i-1
代码如下：
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct item{
int i=0,j=0;
};
int count(vector<int> V,vector<item>& I,int x)
{
int ans=0;
int i=0,j=V.size()-1;
while(i<j)
{
if(V[i]+V[j]==x)
{
ans++;
item temp;
temp.i=i;
temp.j=j;
I.push_back(temp);
i++;
j--;
}
else if(V[i]+V[j]>x)
j--;
else if(V[i]+V[j]<x)
i++;
}
return ans;
}
int main(){
int num=0;
cout<<"请输入数组个数："<<endl;
cin>>num;
cout<<"请依次输入元素："<<endl;
vector<int> V;
vector<item> I;
for(int i=1;i<=num;i++)
{
int temp=0;
cin>>temp;
V.push_back(temp);
}
sort(V.begin(),V.end());
int x=0;
cout<<"请输入待查询值："<<endl;
cin>>x;
int ans=count(V,I,x);
cout<<"符合要求的答案有"<<ans<<"个："<<endl;
for(int a=0;a<=I.size()-1;a++)
cout<<I[a].i<<" "<<I[a].j<<endl;
}别树一帜的写法，大家自行品味~
返回的值是下标~
此外一个新手很容易晕的小细节：
int count(vector<int> V,vector<item>& I,int x)第二个数组I是引用传递！因为要用到返回的结果，而返回值只是一个int，为了不让结果为空，一定要引用传递！！！
2.序列合并
存在两个递增序列A和B，请把他们按序合并到新的数组C中~
这个比较简单，还是使用双指针，按需扫描A和B即可，用每次扫出来的A[i]和B[j]做比较，这样排进C中的数据一定就是有序的~
代码如下：
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
void count(vector<int> A,vector<int> B,int x,int y)
{
int i=0,j=0;
while(i<x&&j<y) //当有某一个序列遍历完之后结束
{
if(A[i]<=B[j]){
cout<<A[i]<<endl;
i++;
}
else{
cout<<B[j]<<endl;
j++;
}
}
//将未遍历完的那一个按序输出~
while(i<x)
{
cout<<A[i]<<endl;
i++;
}
while(j<y)
{
cout<<B[j]<<endl;
j++;
}
}
int main(){
int num1=0,num2=0;
vector<int> A;
vector<int> B;
cout<<"请输入A数组个数："<<endl;
cin>>num1;
cout<<"请依次输入元素："<<endl;
for(int i=1;i<=num1;i++)
{
int temp=0;
cin>>temp;
A.push_back(temp);
}
sort(A.begin(),A.end());
cout<<"请输入B数组个数："<<endl;
cin>>num2;
cout<<"请依次输入元素："<<endl;
for(int i=1;i<=num2;i++)
{
int temp=0;
cin>>temp;
B.push_back(temp);
}
sort(B.begin(),B.end());
count(A,B,num1,num2);
}几个点需要注意一下：
- 这里博主调用了sort函数，保证序列在调用函数的时候肯定是有序的，这个其实是多此一举的操作，为了方便可以乱序输入，实际上题干中给的数据已经是有序的
- 注意上面的while循环存在条件——两个数组都没有被遍历完，因此不难得到其否命题为有个已经被遍历完了。要注意，此处双指针的作用是比较两个数组最小元素的大小，如果有一个全部元素都比完了都没找到一个比另一个大的，则说明这个另一个中的剩余元素一定均大于之前遍历过的，因此直接按序输出即可~
测试一下，没什么bug：
（返回值类型也可以是vector<int> 数组，但是要注意负责存放排序后的值的那个数组一定要引用传参！ ）
二.归并排序
这里介绍最简单的2-路归并排序：
假设现有数列【66,22,33,57,64,27,18】，排序的过程如下：
- 第一步，将所有元素两两划分，然后组内单独排序:【22,66】，【33,57】，【27,64】，【18】
- 第二步，合并相邻两个序列并排序：【22,33,57,66】、【18,27,64】
- 第三步，继续合并并排序【18,22,27,33,57,64,66】——得到答案
不难发现，核心在于如何将两个有序序列合并为一个有序序列——这一操作在上面已经实现~
此外，归并排序的复杂度为N*logN——对于限制N方的题目来说，这是非常好的排序手段！
1.递归实现
首先我们要对上面将有序序列合并的函数做出修改——使其可以在规定的区间内完成有序~
一步一步来，首先将上述修改成返回一个int型vector的函数，本质上没有发生任何改变：
vector<int> count(vector<int> A,vector<int> B)
{
int i=0,j=0;
int x=A.size(),y=B.size();
vector<int> C;
while(i<x&&j<y) //当有某一个序列遍历完之后结束
{
if(A[i]<=B[j]){
C.push_back(A[i]);
i++;
}
else{
C.push_back(B[j]);
j++;
}
}
while(i<x)
{
C.push_back(A[i]);
i++;
}
while(j<y)
{
C.push_back(B[j]);
j++;
}
return C;
}然后需要注意，这时候参数要改了这里只是要实现：将某个数组中两个无序的区间合成为同一个有序的区间（数组），因此需要传入的参数应该是5个：目标数组，然后是4个区间端点！
合并函数如下：
vector<int> merge(vector<int> V,int x1,int y1,int x2,int y2)
{
int i=x1-1,j=x2-1;//下标和位序相差一，这里符合惯性思维的赋值方式~
vector<int> V1;
while(i<=y1-1&&j<=y2-1) //当有某一个序列遍历完之后结束
{
if(V[i]<=V[j]){
V1.push_back(V[i]);
i++;
}
else{
V1.push_back(V[j]);
j++;
}
}
while(i<=y1-1)
{
V1.push_back(V[i]);
i++;
}
while(j<=y2-1)
{
V1.push_back(V[j]);
j++;
}
return V1;
}在main函数测试一下效果：
int main(){
int num1=0,num2=0;
vector<int> A;
vector<int> B;
cout<<"请输入A数组个数："<<endl;
cin>>num1;
cout<<"请依次输入元素："<<endl;
for(int i=1;i<=num1;i++)
{
int temp=0;
cin>>temp;
A.push_back(temp);
}
int x1=0,x2=0,y1=0,y2=0;
cout<<"请依次输入4个区间：";
cin>>x1>>y1>>x2>>y2;
vector<int> C;
C=merge(A,x1,y1,x2,y2);
for(int i=0;i<=C.size()-1;i++)
cout<<C[i]<<" ";
}想起来英语有一个单词叫做perfect~
上面的区间就是我们高中学的数列中正常的位序——博主在代码中已经做了换算，大家直接输入位序即可！
不过细心的同学可能会发现——如果我输入的A先入为主是有序的，还需要归并排序干嘛？这里实现的是两个区间，区间是人为给定好的，但是在归并排序里面，或者说这种2路归并排序，实际上参数值是某种固定的顺序。因此通过递归，将这个数组的区间不断细分，细分到只剩下一个元素的时候，实际上一下子就能比较出来，然后层层递进回来，上一层递归返回来的数组本身就是一个有序序列！
因此来写我们的递归函数：
void mergeSort(vector<int> &V,int left,int right)
{
if(left<right)
{
int mid =(left+right)/2;
mergeSort(V,left,mid);
mergeSort(V,mid+1,right);
merge(V,left,mid,mid+1,right);
}
} 参数类型不同的时候代码可能会有不同的结果，大家自行尝试~
2.非递归实现
非递归的大家自己看一下思路吧，博主能力有限，由于返回值类型的有效性，目前还没有较完美的实现~
三.快速排序
依旧是一个复杂度为N*logN的排序算法。
这部分理论先放一下，直接上实现代码：
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int part(int* r, int low, int hight) //划分函数
{
int i = low, j = hight, pivot = r[low]; //基准元素
while (i < j)
{
while (i<j && r[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
{
j--;
}
if (i < j)
{
swap(r[i++], r[j]); //r[i]和r[j]交换后 i 向右移动一位
}
while (i < j && r[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
{
i++;
}
if (i < j)
{
swap(r[i], r[j--]); //r[i]和r[j]交换后 i 向左移动一位
}
}
return i; //返回最终划分完成后基准元素所在的位置
}
void Quicksort(int* r, int low, int hight)
{
int mid;
if (low < hight)
{
mid = part(r, low, hight); // 返回基准元素位置
Quicksort(r, low, mid - 1); // 左区间递归快速排序
Quicksort(r, mid+1, hight); // 右区间递归快速排序
}
}
int main()
{
int a[10001];
int N;
cout << "请输入要排序的数据的个数： " << endl;
cin >> N;
cout << "请输入要排序的数据： " << endl;
for (int i = 0; i < N; i++)
{
cin >> a[i];
}
cout << endl;
Quicksort(a, 0, N - 1);
cout << "排序后的序列为： " << endl;
for (int i = 0; i < N; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}写在最后：单说思想本身，个人感觉归并和快排已经是初学者除了DP最难的算法了，实现起来考虑到返回值类型什么的会更加困难一些。但考虑到比N方还要低的复杂度，这两种算法的性价比相当之高！这里先留个坑位，之后理论部分补充一些王道408的部分会更好一些~
对于基础的双指针算法，没什么理解起来的难度，需要注意的是等号的选取范围，以及while循环执行下去的条件，不同题目可能不尽相同。
原文地址：https://blog.csdn.net/jsl123x/article/details/140476353
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！