第k小数

注意细节即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<queue>
#include<iomanip>

using namespace std;
int n,k,ans;
int a[5000010];
long long read(){
	long long x=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')h=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*h;
}

void q_sort(int l,int r){
	if(l==r){
		ans=a[l];
		return ;
	}
	int mid=a[(l+r)>>1];
	int i=l,j=r;
	do {
		while(a[i]<mid&&i<=j)i++;  // detail 1
		while(a[j]>mid&&i<=j)j--;  // detail 2
		if(i<=j){    // detail 3
			swap(a[i],a[j]);
			i++,j--;
		}
	}while(i<=j);    // detail 4
//	cout<<i<<","<<j<<":"; 
//	for(int i=1;i<=n;i++){
//		cout<<a[i]<<" ";
//	}
//	cout<<endl;
	if(k==j+1){    // detail 5
		ans=a[j+1];
		return ;
	}
	else if(k<=j){   // detail 6
		q_sort(l,j);
	}
	else {
		q_sort(i,r);     // detail 7
	}
}

int main(){
//	freopen("","r",stdin);
//	freopen("","w",stdout);
	n=read();k=read()+1;
	for(int i=1;i<=n;i++)a[i]=read();
	
	q_sort(1,n);
	cout<<ans<<endl;
	return 0;
}

注意细节!!!

或者使用函数:nth_element(a+start,a+question,a+end);
结果为:a[question]

Example:

int a[50]={0,1,2,3,4,5,6,7,8,9,10};
nth_element(a+1,a+10,a+11);
cout<<a[10]<<endl;

注意!此函数会把数组顺序打乱!

上一篇:c# – 我怎么知道Kestrel何时开始收听?


下一篇:[07]ASP.NET Core 进程外(out-of-process)托管