题解 | #寻找第K大#
寻找第K大
http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
class Solution {
public:
int quick_sort(vector<int> &data, int left, int right){
int base = data[left];
while (left < right)
{
while (left < right && data[right] >= base)
--right;
data[left] = data[right];
while (left < right && data[left] <= base)
++left;
data[right] = data[left];
}
data[left] = base;
return left;
}
int findKth(vector<int> a, int n, int K) {
int low = 0;
int high = n -1;
K = n - K;
while (true)
{
int index = quick_sort(a, low, high);
if (index == K)
return a[index];
if (index < K)
low = index + 1;
if (index > K)
high = index - 1;
}
}
};
