利用快排中的Partition
算法导论中经典的partition
class Finder { public: int findKth(vector<int> a, int n, int K) { // write code here return findK(a, 0, n-1, K); } int findK(vector<int> &a, int L, int R, int K){ int mid = partition(a, L, R); int nRight = R - mid + 1; if(K == nRight){ return a[mid]; }else if(K > nRight){ return findK(a, L, mid - 1, K - nRight); } else{ return findK(a, mid + 1, R, K); } } int partition(vector<int> &a, int L, int R){ int v = a[R]; int j = L-1; for(int i = L; i <= R; i++){ if(a[i] <= v){ j++; swap(a[i], a[j]); } } return j; } };