AcWing基础算法(一)

快速排序

题目

给定你一个长度为 nn 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 nn。

第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 nn 个整数，表示排好序的数列。

数据范围

1≤n≤1000001≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

思路

找到一个衡量值，将该值的左边变换为小于它的值，右边变换为大于它的值，然后遍历。

实现

现将指针指向数据的两侧，然后寻找一个中间值。

int l=0;//指向最左侧的指针
int r=n-1;//指向最右侧的指针（n为我们输入数据的个数）
int x=q[(l+j)/2];//衡量的中间值

如果一开始左侧指针的位置就大于右侧指针了，那么我们应该直接结束。

左侧指针找出比衡量值大的数然后停止，右侧指针找出比衡量值小的数然后停止，如果此时左侧指针的位置小于右侧指针的位置则将左右两指针指向的数据对换。

if(l>=r)return;
while(l<r){
	while(q[l]<x)l++;
	while(q[r]>x)r--;
	if(l<r){
		int tmp=q[l];//中间变量
   	 q[l]=q[r];
    	q[l]=tmp;
	}
}

将代码封装为函数进行递归调用，使所有的值都有机会作为衡量值。

void quick(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){
            int tmp=q[i];
            q[i]=q[j];
            q[j]=tmp;
        }
    }
    
    quick(q,l,j);
    quick(q,j+1,r);
}

最终代码

#include<stdio.h>
#define N 100010//常量
int n;
int q[N];

void quick(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){
			int tmp=q[i];
			q[i]=q[j];
			q[j]=tmp;
		}
	}
	quick(q,l,j);
	quick(q,j+1,r);
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&q[i]);
	}
	
	quick(q,0,n-1);
	for(int i=0;i<n;i++){
		printf("%d ",q[i]);
	}
}

归并排序

题目

给定你一个长度为 nn 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 nn。

第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 nn 个整数，表示排好序的数列。

数据范围

1≤n≤1000001≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

思路

采用分治的思想，将数据一分为二，比较出两数组的最小值。

实现

定义两个指针，分别指向两个分开后两数据的头部。

int mid=(l+r)/2;//l为左端点，r为右端点
int i=l,j=mid+1;

将数据从中间一分为二；

merge(q,l,mid),merge(q,mid+1,r);//merge为我们定义的函数

利用我们定义的指针对刚刚分为两个的数据进行比较，从左到右如果哪个数据小就先将数据存入临时数组tmp中。如果在比较完成后发现有的数据并没有完全存入到临时数组tmp中，则利用循环将数据存入

int k=0;
while(i<=mid&&j<=r){
    if(q[i]<=q[j])tmp[k++]=q[i++];
    else tmp[k++]=q[j];
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];

最终代码

#include<stdio.h>
#define N 100010
int n;
int q[N],tmp[N];

void merge(int q[],int l,int r){
	if(l>=r)return;
	
	int mid=(l+r)/2;
	
	merge(q,l,mid),merge(q,mid+1,r);
	
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j])tmp[k++]=q[i++];
		else tmp[k++]=q[j++];
	}
	while(i<=mid)tmp[k++]=q[i++];
	while(j<=r)tmp[k++]=q[j++];
	for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&q[i]);
	}
	
	merge(q,0,n-1);
	for(int i=0;i<n;i++){
		printf("%d ",q[i]);
	}
}

整数二分

题目

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 nn 和 qq，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 kk，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

思路

判断区间的中间值是否满足某个条件，然后将区间中间值变为左边界或有边界再次进行判断，直至区间长度缩短为一

实现

在左边界小于右边界的条件下，找到区间长度的中间值，然后和题目的条件进行判断，如果中间值大于给出的条件（数组按照升序排列），那么将中间值变为左边界，右边界不变。此时我们找出的是左边界

int x;
scanf("%d",&x);
int l=0,r=n-1;//l为左边界,r为右边界，n为输入的数据个数
while(l<r){
    int mid=(l+r)/2;
    if(q[mid]>=x)r=mid;
    else l=mid+1;
}

如果找出的左边界和给出的条件相等就输出该边界的值，并进行右边界的查找，如果查找的左边界和给出的条件不相等则输出-1 -1然后结束程序。

if(q[l]!=x){
    printf("-1 -1");
}
else{
    while(l<r){
        int mid=(l+r+1)/2;//如果不加一的话，当l=r-1时，mid始终等于l，会变成死循环
        if(q[mid]<=x)l=mid;
        else r=mid-1;
    }
    printf("%d",r);
}

最终代码

#include<stdio.h>

#define N 100010

int n,m;
int q[N];

int main(){
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++)scanf("%d",&q[i]);
	
    //左边界
	while(m--){
		int x;
		scanf("%d",&x);
		
		int l=0,r=n-1;
		while(l<r){
			int mid=(l+r)/2;
			if(q[mid]>=x)r=mid;
			else l=mid+1;		
		}
		
		if(q[l]!=x){
			printf("-1 -1\n");
		}
        //右边界
		else{
			printf("%d ",l);
			
			int l=0,r=n-1;
			while(l<r){
				int mid=(l+r+1)/2;
				if(q[mid]<=x)l=mid;
				else r=mid-1;
			}
			printf("%d\n",r);
		}
	}
	return 0;
}

小数二分

题目

对输入的数据开平方

思路

和整数二分一样，但是不需要处理边界问题。

实现

在左右边界距离大于10的负6次方时，对边界进行划分

double x;
sacnf("%lf",&x);
double l=0,r=x;
while(r-l>1e-6){
    double mid=(r+l)/2;
    if(mid*mid>=x)r=mid;
    else l=mid;
}
printf("%lf",l)