two pointers思想

利用问题本身与序列的特性，利用两个下标i、j对序列进行同向或反向扫描，以降低时间复杂度（一般是O（n）的复杂度）。

一、双指针题目

1.两数相加

递增的正整数序列中，如{1、2、3、4、5、6}中找出满足两个数相加之和为M=8的所有组合。

思路
最直观的思路是两层for循环暴力遍历，if判断两个数之和是否为M，如果不是，则继续枚举，显然时间复杂度很高。
根据题目的序列是递增的特点，可以使用两个下标——下标i指向序列的第一个元素，下标j指向序列的最后一个元素。
根据a[i]+a[j]和M的大小得到三种情况，使i不断向右移动，使j不断向j移动，直到i大于等于j才停止。

时间复杂度分析：
i和j的移动次数之和最多为n次，所以时间复杂度为O(n)。

代码

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[10]={1,2,3,4,5,6,7,8,9,10};
	int i=0,j=9;
	int m=8;
	while(i<j){
		if(a[i]+a[j]==m){
			printf("%d %d\n",i,j);
			i++;
			j--;
		}else if(a[i]+a[j]<m){
			i++;	
		}else{
			j--;
		}
	}
	system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

输出的结果：

2.就地删除or移除元素

【LeetCode26】删除排序数组中的重复项（双指针）

【LeetCode27】移除元素（双指针）

3.注意双指针方向

同向：
【LeetCode141】环形链表（双指针）

反向：
【LeetCode11】盛最多水的容器（反向双指针）

二.常见算法

1.序列合并

基础，合并两个递增序列成递增序列。

int merge(int A[],int B[],int C[],int n,int m){
	int i=0,j=0,index=0;//i指向A[0],j指向B[0]
	while(i<n&&j<m){
		if(A[i]<=B[j]){
			C[index++]=A[i++];//将A[i]加入到序列C中
		}else{
			C[index++]=B[i++];	
		}
	}
	while(i<n) C[index++]=A[i++];
	while(j<n) C[index++]=b[j++];//将序列B剩下的元素加入到序列C中
	return index;//返回序列C的长度
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

2.归并排序

下面以二路归并为栗子：

3.递归版本

merge函数在上面的基础上改动。
思想：利用mergeSort函数递归划分左子区间和右子区间，不断划分到最后的情况是，1个数就是一个“有序序列”，而将这两个“有序序列”用merge进行合并…merge函数实现将左子区间和右子区间合并。

const int maxn=100;
//将数组A的[L1,R1]与[L2,R2]区间合并为有序区间（此处L2即为R1 +1）
int merge(int A[],int L1,int R2,int L2,int R2){
	int i=L1,j=L2;//i指向A[L1],j指向A[L2]
	int temp[maxn],index=0;//temp临时存放合并后的数组，index为其下标
	while(i<=R1 && j<=R2){
		if(A[i]<=B[j]){
			temp[index++]=A[i++];//将A[i]加入到序列temp中
		}else{
			temp[index++]=A[j++];//将A[j]加入到序列temp中	
		}
	}
	while(i<=R1) temp[index++]=A[i++];//将[L1,R1]的剩余元素加入序列temp
	while(j<R2) temp[index++]=A[j++];//将序列B剩下的元素加入到序列temp中
	for(i=0;i<index;i++){
		A[L1+i]=temp[i];//将合并后的序列赋值回数组A
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

而mergeSort函数（递归实现）：

void mergeSort(int A[],int left,int right){
	if(left<right){//只要left小于right
		int mid=(left+right)/2;
		mergeSort(A,left,mid);//递归，将左子区间归并排序
		mergeSort(A,mid+1,right);//递归，将右子区间归并排序
		merge(A,left,mid,mid+1,right);
	}
}	

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

4.非递归版本

每次分组时组内元素个数上限都是2的幂次。
令步长step的初值=2，然后将数组中每step个元素作为一组，将其内部进行排序（即把左step/2个元素与右step/2个元素进行合并，若元素个数不超过step/2，则不超过），再令step乘以2，重复上面的操作，直到step/2超过元素个数n。

void mergeSort(int A[]){
	//step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取
	for(int step=2;step/2<=n;step*=2){
		//每step个元素一组，组内step前step/2和step/2个元素进行合并
		for(int i=1;i<=n;i+=step){//对每一组
			int mid=i+step/2-1;//左子区间元素个数为step/2
			if(mid+1<=n){//右子区间存在元素则合并
				//左子区间为[i,mid],右子区间为[mid+1,min(i+step-1,n)]
				merge(A,i,mid.mid+1,min(i+step-1,n));
			}
		}
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

如果题目中只要求给出归并排序每一趟结束时的序列，可以使用sort函数替代merge函数（只要时间限制允许）。

void mergeSort(int A[]){
	//step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取
	for(int step=2;step/2<=n;step*=2){
		//每step个元素一组，组内[i,min(i+step,i)]进行排序
		for(int i=1;i<=n;i+=step){
			sort(A+i,A+min(i+step,n+1));
		}
		//此处可以输出归并排序的某一趟结束的序列
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

5.快速排序

回看基础算法。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112392768