快排子问题
题目 第K个数
思路分析
对于快排的递归两边做改进 第k个数只存在于一边 那么另一边就可以不完全排序 判断一下 只做一个递归调用即可
如何判断？
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=100010;
int n;
int q[N];
int k;
int quick_sort(int l,int r,int k){
if(l>=r) return q[l];
int i=l-1,j=r+1,m=q[l+r>>1];
while(i<j){
do{
i++;
}while(q[i]<m);
do{
j--;
}while(q[j]>m);
if(i<j)
swap(q[i],q[j]);
}
int sl=j-l+1;
if(k<=sl)
return quick_sort(l,j,k);
return quick_sort(j+1,r,k-sl);
/*
本来是要走两遍的 但是因为是找第k小 它只存在于一边 所以只需要对一边完全排序以找到k位置
如果在左边 就不用管右边 第K小的数仍在k位置
如果在右边 左边可以不用完全排序 但是数量不会变
此时第k小的数 对于右半边来说 其实是第（k-左边个数）小的数
*/
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>q[i];
cout<<quick_sort(0,n-1,k);
return 0;
}
💬 评论