题解 | #寻找第K大#
寻找第K大
http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
快速排序法
注意第K大实际上是排序后的第K-1位 晕死
class Solution {
public:
int partition(vector<int> &a, int left, int right){
int first = a[left];
while(left < right){
while(left < right && first >= a[right]){
right --;
}
if(first < a[right]){
a[left++] = a[right];
}
while(left <right && a[left] >= first){
left ++;
}
if(a[left] < first){
a[right--] = a[left];
}
}
a[left] = first;
return left;
}
int quickSort(vector<int> &a, int left, int right, int K){
int pos = partition(a, left, right);
if(pos == K-1) return a[K-1];
else if(pos < K-1){
return quickSort(a, pos+1, right, K);
}else{
return quickSort(a, left, pos-1, K);
}
}
int findKth(vector<int> a, int n, int K) {
int res = quickSort(a, 0, n-1, K);
return res;
}
}; 
