本文主要是介绍强化阶段 Day 15 算法笔记 4.6 two pointers（2），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

1.将数组分成大于或小于某个数的两个部分

2.快速排序

3.Perfect Sequence

4.Insert or Merge

5.Median

6.Find Coins

1.将数组分成大于或小于某个数的两个部分

int partition(int martix[];int left;int right){
	int temp=martix[left];
	while(left<right){
		while(left<right&&martix[right]>temp) right--;
		martix[left]=martix[right];
		while(left<right&&martix[left]<=temp) left++;
		martix[right]=martix[left];
	}
	martix[left]=temp;
	return left;
}

2.快速排序

void quicksort(int martix[],int left,int right){
	if(left<right){
		pos=partition(martix,left,right);
		quicksort(martix,left,pos-1);
		quicksort(martix,pos+1,right);
	}
}

3.Perfect Sequence

这个做法比之前的二分法要优雅多了

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;

int main(){
	
	long long n,p;
	scanf("%d %d",&n,&p);
	int martix[100005];
	for(int i=0;i<n;i++){
		scanf("%d",&martix[i]);
	}
	sort(martix,martix+n);
	int j=0,max_=-1;
	for(int i=0;i<n;i++){
		while(martix[j]<=p*martix[i]&&j<n) j++;
		if(j-i>max_){
			max_=j-i;
		}
	}
	printf("%d",max_);

	return 0;

}

4.Insert or Merge

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;

int origin[105],changed[105],temps[105];
int n;

bool issame(){
	for(int i=0;i<n;i++){
		if(changed[i]!=temps[i]) return false;
	}
	return true;
}

bool print(){
	for(int i=0;i<n;i++){
		printf("%d",temps[i]);
		if(i!=n-1) printf(" ");
	}
	printf("\n");
}

int insert(){
	bool flag=false;
	for(int i=1;i<n;i++){
		if(issame()) flag=true;
		int temp=temps[i],pos=i;
		while(pos>0&&temps[pos-1]>temp){
			temps[pos]=temps[pos-1];
			pos--;
		}
		temps[pos]=temp;
		if(flag) return true;
	}
	return false;
}

void merge(){
	bool flag=false;
	for(int step=2;step/2<=n;step*=2){
		if(step!=2&&issame()) flag=true;
	for(int i=0;i<n;i+=step){
		sort(temps+i,temps+min(i+step,n));
	}
	if(flag){
		print();
		return;
	}
}
}

int main(){
	
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&origin[i]);
		temps[i]=origin[i];
	}
	for(int i=0;i<n;i++){
		scanf("%d",&changed[i]);
	}
	if(insert()){
		printf("Insertion Sort\n");
		print();
	}else{
		printf("Merge Sort\n");
		for(int i=0;i<n;i++){
			temps[i]=origin[i];
		}
		merge();
	}
	return 0;

}

5.Median

要注意一下inf的使用，要不然会有其中一个数组的元素很少而且还都非常小的情况会导致两个点无法通过

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;

int main(){
	
	int n,m,martix1[200005],martix2[200005];
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&martix1[i]);
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&martix2[i]);
	}
	
	int i=0,j=0,count=0;
	int final=(n+m-1)/2;
	martix1[n]=0x7fffffff;
	martix2[m]=0x7fffffff;
	while(count!=final){
		if(martix1[i]>=martix2[j]) j++;
		else i++;
		count++;
	}
	if(martix1[i]<martix2[j]){
		printf("%d",martix1[i]);
	}else{
		printf("%d",martix2[j]);
	}
	
	return 0;

}

6.Find Coins

双指针法牛逼！！！

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;

int main(){
	
	int n,m;
	int martix[100005];
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&martix[i]);
	}
	sort(martix,martix+n);
	int i=0,j=n-1;
	while(i<j){
		if(martix[i]+martix[j]>m) j--;
		else if(martix[i]+martix[j]<m) i++;
		else break;
	}
	
	if(i<j){
		printf("%d %d",martix[i],martix[j]);
	}else{
		printf("No Solution");
	}
	return 0;

}

这篇关于强化阶段 Day 15 算法笔记 4.6 two pointers（2）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！