AcWing basic algorithm (I)
Quick sort
subject
Give you a sequence of integers with length nn.
Please use quick sort to sort this sequence from small to large.
And output the ordered sequence in order.
Input format
The input consists of two lines. The first line contains the integer nn.
The second row contains nn integers (all integers are in the range of 1 ∼ 1091 ∼ 109), representing the whole sequence.
Output format
The output consists of one line, including nn integers, representing the ordered sequence.
Data range
1≤n≤1000001≤n≤100000
Input example:
5 3 1 2 4 5
Output example:
1 2 3 4 5
thinking
Find a measurement value, transform the left side of the value into a value less than it, and the right side into a value greater than it, and then traverse.
realization
Now point the pointer to both sides of the data, and then look for an intermediate value.
int l=0;//Pointer to the far left int r=n-1;//Pointer to the rightmost side (n is the number of data we input) int x=q[(l+j)/2];//Intermediate value of measurement
If the position of the left pointer is larger than the right pointer at the beginning, we should end directly.
The left pointer finds out the number larger than the measured value and then stops, and the right pointer finds out the number smaller than the measured value and then stops. If the position of the left pointer is smaller than the position of the right pointer at this time, the data pointed by the left and right pointers will be exchanged.
if(l>=r)return;
while(l<r){
while(q[l]<x)l++;
while(q[r]>x)r--;
if(l<r){
int tmp=q[l];//Intermediate variable
q[l]=q[r];
q[l]=tmp;
}
}
Encapsulate the code as a function for recursive calls, so that all values have the opportunity to be measured.
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);
}
Final code
#include<stdio.h>
#define N 100010 / / constant
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]);
}
}
Merge sort
subject
Give you a sequence of integers with length nn.
Please use merge sort to sort this sequence from small to large.
And output the ordered sequence in order.
Input format
The input consists of two lines. The first line contains the integer nn.
The second row contains nn integers (all integers are in the range of 1 ∼ 1091 ∼ 109), representing the whole sequence.
Output format
The output consists of one line, including nn integers, representing the ordered sequence.
Data range
1≤n≤1000001≤n≤100000
Input example:
5 3 1 2 4 5
Output example:
1 2 3 4 5
thinking
Using the idea of divide and conquer, divide the data into two and compare the minimum values of the two arrays.
realization
Define two pointers to the headers of two separated data.
int mid=(l+r)/2;//l is the left endpoint and r is the right endpoint int i=l,j=mid+1;
Split the data in two from the middle;
merge(q,l,mid),merge(q,mid+1,r);//Function defined for us by merge
Use the pointer we defined to compare the data just divided into two. From left to right, if which data is small, first store the data in the temporary array tmp. If it is found that some data is not completely stored in the temporary array tmp after the comparison is completed, the data is stored in the temporary array tmp using a loop
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++];
Final code
#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]);
}
}
Integer dichotomy
subject
Given an array of integers of length n in ascending order and q queries.
For each query, the start and end positions of an element k are returned (the positions are counted from 00).
If the element does not exist in the array, - 1 - 1 is returned.
Input format
The first line contains integers nn and qq, indicating the length of the array and the number of queries.
The second line contains n integers (all in the range of 1 ∼ 100001 ∼ 10000), representing the complete array.
Next q lines, each containing an integer kk, represent a query element.
Output format
There are q rows in total, and each row contains two integers, indicating the starting position and ending position of the element.
If the element does not exist in the array, - 1 - 1 is returned.
Data range
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
Input example:
6 3 1 2 2 3 3 4 3 4 5
Output example:
3 4 5 5 -1 -1
thinking
Judge whether the intermediate value of the interval meets a certain condition, and then change the intermediate value of the interval into a left boundary or a boundary for judgment again until the interval length is shortened to one
realization
Under the condition that the left boundary is less than the right boundary, find the middle value of the interval length, and then judge with the condition of the topic. If the middle value is greater than the given condition (the array is arranged in ascending order), the middle value will become the left boundary, and the right boundary will remain unchanged. At this point, we find the left boundary
int x;
scanf("%d",&x);
int l=0,r=n-1;//l is the left boundary, r is the right boundary, and n is the number of input data
while(l<r){
int mid=(l+r)/2;
if(q[mid]>=x)r=mid;
else l=mid+1;
}
If the found left boundary is equal to the given condition, output the value of the boundary and search the right boundary. If the found left boundary is not equal to the given condition, output - 1 - 1, and then end the program.
if(q[l]!=x){
printf("-1 -1");
}
else{
while(l<r){
int mid=(l+r+1)/2;//If you do not add one, when l=r-1, mid is always equal to L, which will become an endless loop
if(q[mid]<=x)l=mid;
else r=mid-1;
}
printf("%d",r);
}
Final code
#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]);
//Left boundary
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");
}
//Right boundary
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;
}
Decimal dichotomy
subject
Square the input data
thinking
It is the same as integer bisection, but there is no need to deal with the boundary problem.
realization
When the distance between the left and right boundaries is greater than the negative 6th power of 10, the boundary is divided
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)