递归解法,把比标准数小的放左边, 比标准数大的放右边,然后就把问题缩减到更小的规模了,不过就我的渣渣代码来看,貌似还达不到o(2n)的下界,写完了才发现自己连快排都写不熟,长期用STL偷懒的副作用啊,不过其实我记得STL是有nth_element的函数的,不过会写总比不会强,哈哈
template<typename T> void Kth(vector<T> & v,int k,int l,int r) { if(l>=r)return; T t = v[l]; int left = l ,right = r; T key = v [left]; while(left<right) { while(left<right&&v[right]>t) { right--;; } v[left]=v[right]; if(left<right)left++; while(left<right&& v[left]<t) { left++; } v[right]=v[left]; if(left<right)right--; } v[left]=key;
if(left>k) Kth(v,k,l,left-1); else Kth(v,k,left+1,r); }