這個(gè)問題的解決方法很多啊，一下列舉一下
1 基于排序的傳統(tǒng)方法 O(nlogn)
如果你只需要找一次第k小的數(shù)，這不是一個(gè)好方法。。。如果你要找n次，還是用排序吧
2 Las Vegas概率算法
也可以稱之為隨機(jī)化算法，其算法的特點(diǎn)優(yōu)點(diǎn)類似于快速排序，都是需要選擇pivot，然后進(jìn)行劃分。把一個(gè)序列劃分為3部分，x 小于x 和大于x的。。然后根據(jù)k的取值，進(jìn)行遞歸計(jì)算。
畢竟是LasVegas算法，其最壞時(shí)間復(fù)雜度很差，是O(n^2)。。當(dāng)然，平均復(fù)雜度非常好 O(n) 如果學(xué)過隨機(jī)化算法，證明不難！
3 基于r劃分的O(n)算法
這個(gè)算法可以說是一個(gè)trick，他的思想就是想優(yōu)化LasVegas算法中的pivot選擇。。所以才會(huì)有這個(gè)算法。假設(shè)我們把r取成5的話，以每5個(gè)元素為子集劃分源數(shù)組，然后對(duì)每個(gè)子集排序求出中位數(shù)，這樣的中位數(shù)集合組成一個(gè)新的序列M，對(duì)M遞歸的求解其中位數(shù)p，得到的p即為劃分點(diǎn)。p將源數(shù)組劃分為3部分：
* s1：所有小于p的元素
* s2: 所有等于p的元素
* s3: 所有大于p的元素
下一輪迭代的時(shí)候根據(jù)輸入的level參數(shù)判斷該剪去哪部分元素。
這樣，每一輪迭代至少剪去n/4的元素（畫個(gè)中位數(shù)排列的圖出來就容易看出），則最壞情況下的時(shí)間復(fù)雜度表示為：
T(n)<=T(3n/4)+T(n/5)+O(n)
其中
* T(3n/4)是下一輪迭代的最大數(shù)據(jù)量情況下的時(shí)間復(fù)雜度
* T(n/5)是求尋找中位數(shù)組成集合的中位數(shù)的時(shí)間復(fù)雜度
利用歸納法，可以很清楚的證明出來T(n) <=20cn (c為常數(shù))
基于r劃分的算法，其最壞時(shí)間復(fù)雜度是O(n)。。感覺是不是很優(yōu)秀！但是，優(yōu)秀的代價(jià)是你的常數(shù)因子太大了！！！
平時(shí)在選擇算法的時(shí)候，基本上可以說是一邊倒的選擇Las Vegas算法！
此外，在解決問題的時(shí)候，最好看清楚題目的情景，如果題目要求n個(gè)數(shù)中的第k個(gè)數(shù)，但是k取從1-n。。。那么還是用基于排序的吧。。。畢竟做了O(nlogn)的工作之后，每次都是O(1)搞定。。而LasVegas算法和基于r劃分的方法都要O(n^2)
基于LasVegas算法的代碼：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define Max 10000
int cnt=0;
int select( int *a, int b, int e, int k) //從b到e
{
cnt++;
if (b==e) return a[b];
int x=a[b+rand()%(e-b+1)],i=b,j=e;
i--;j++;
while (i<j)
{
while (a[++i] < x); while (a[--j] > x);
if (i<j)std::swap(a[i],a[j]);
}
if (j==e)j--;i=j-b+1;
if (k <=i) return select(a,b,j,k);
else return select(a,j+1,e,k-i);
}
int main()
{
int a[Max];
for(int i=0;i<Max;i++)
a[i]=i;
random_shuffle(a,a+Max);
int b[Max];
for(int i=0;i<Max;i++)
b[i]=a[i];
cout<<endl;
vector<int> C;
for(int i=0;i<Max;i++)
{
cnt=0;
select(a,0,Max-1,i);
for(int i=0;i<Max;i++)
a[i]=b[i];
C.push_back(cnt);
}
sort(C.begin(),C.end());
cout<<C[0]<<endl;
cout<<C[C.size()-1]<<endl;
return 0;
}
從代碼結(jié)果可以看出LasVegas算法表現(xiàn)還是很優(yōu)秀的，畢竟10000個(gè)數(shù)，最深遞歸層次是35層！
此外，當(dāng)然求第k小元素的各種復(fù)雜數(shù)據(jù)結(jié)構(gòu)也可以做，而且效率也可以，看第四種方法： (這種方法等以后再總結(jié)吧。。)
回顧樹狀數(shù)組的定義，注意到有如下兩條性質(zhì)：
一，c[ans]=sum of A[ans-lowbit(ans)+1 ... ans];
二，當(dāng)ans=2^k時(shí)，
c[ans]=sum of A[1 ... ans];
下面說明findK(k)如何運(yùn)作：
1，設(shè)置邊界條件ans,ans'<maxn且cnt<=k；
2，初始化cnt=c[ans]，其中ans=2^k且k為滿足邊界條件的最大整數(shù)；
3，找到滿足邊界條件的最大的ans'使得ans'-lowbit(ans')=ans，即ans'滿足c[ans']=A[ans+1 .. ans']（根據(jù)性質(zhì)一），只要將c[ans']累加到cnt中（此時(shí)cnt=sum of A[1 ... ans']，根據(jù)性質(zhì)二），cnt便可以作為k的逼近值；
4，重復(fù)第3步直到cnt已無法再逼近k，此時(shí)ans剛好比解小1，返回ans+1。
因此findk(k)的實(shí)質(zhì)就是二分逼近
/**********************************
樹狀數(shù)組實(shí)現(xiàn)查找K小的元素
經(jīng)典。
限制：數(shù)據(jù)范圍在1<<20 以內(nèi)
***********************************/
#include <iostream>
using namespace std;
#define maxn 1<<20
int n,k;
int c[maxn];
int lowbit(int x){
return x&-x;
}
void insert(int x,int t){
while(x<maxn){
c[x]+=t;
x+=lowbit(x);
}
}
int find(int k){
int cnt=0,ans=0;
for(int i=20;i>=0;i--){
ans+=(1<<i);
if(ans>=maxn || cnt+c[ans]>=k)ans-=(1<<i);
else cnt+=c[ans];
}
return ans+1;
}
void input(){
memset(c,0,sizeof(c));
int t;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&t);
insert(t,1);
}
printf("%d\n",find(k));
}
int main(){
int cases;
scanf("%d",&cases);
while(cases--){
input();
}
return 0;
}