链接：点击打开链接
题意：求无序数组的第k小
代码：
#include <queue> #include <vector> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; int n,k,ans,a[1000005]; int change(int ll,int rr){ int tt=a[ll]; while(ll<rr){ while(ll<rr&&a[rr]>tt) rr--; a[ll]=a[rr]; while(ll<rr&&a[ll]<tt) ll++; a[rr]=a[ll]; } a[ll]=tt; return ll; } void cal(int ll,int rr){ int op=change(ll,rr); if(op==k){ ans=a[op]; return; } else if(op>k) cal(ll,op-1); else cal(op+1,rr); } int main(){ //主要思想还是基于快排，就是在排序的时候 int i; //根据左右区间的大小从而只在一个区间继续排序 while(scanf("%d%d",&n,&k)!=EOF){ //这样做相比直接排序求第k小的复杂度的常数要小 for(i=1;i<=n;i++) //期望复杂度为O(n+n/2+n/4+...+1)=O(2N) scanf("%d",&a[i]); //但是既然是基于快排的思想，我们依然可以构造 if(k<=0||k>n){ //一个递增或递减的数列叉掉这个算法 puts("-1"); //所以我们依然可以先随机化一下再进行操作 continue; } cal(1,n); printf("%d\n",ans); } return 0; }