60分超时了,求指导
查看原帖
60分超时了,求指导
940154
Qian1239楼主2023/2/9 15:49
#include <iostream>
#include<cstdio>
#include <vector>
using namespace std;
int a[5000005];


int select (int left, int right, int k){
	if(left>=right) return a[left];
	int i=left;	int j=right+1;
	int pivot=a[left];
	while(true){
		do{	i=i+1;}while(a[i]<pivot);
		do{	j=j-1;}while(a[j]>pivot);
		if(i>=j) break;
		swap(a[i],a[j]);
	}
	if(j-left+1==k) return pivot;
	a[left]=a[j];
	a[j]=pivot;
	if(j-left+1<k) //j-left+1 :左区元素的个数
		return select(j+1,right,k-(j-left)-1); //在右区中找
	else
		return select(left,j-1,k);
}

int main(){
	int n,k;
	cin>>n>>k;
    k=k+1;
	for(int i=0;i<n;i++)
	cin>>a[i];

	cout<<select(0,n-1,k)<<endl;
}
2023/2/9 15:49
加载中...