题解 | #寻找第K大#
寻找第K大
http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
第K大，题目要求使用快排的思想。那么先用快排实现，然后在优化。
写一个快排排序，然后取排序后的第K大的数。
还没完啊，先分析一下：
1.输入一个数组，一个range的其起始位置跟结束位置，随便找一个哨兵，那么进行一番操作之后，
比哨兵大的数都放到右边，比哨兵小的数都放到左边。
2.假设第一次操作完成，右边比哨兵大的数有len个，那么如果len小于K，右边肯定不需要继续排序了，因为第K大的数肯定在左边，
而且在左边的第K-len-1大的数，（需要排除哨兵，多减去一个1）。如果len比K大，那么左边不需要排序了，第K大的数肯定在右边。
3.递归的找下去。处理好边界。
class Solution {
public:
int findKth(vector<int> a, int n, int K) {
// write code here
if(a.size() < K){
return -1;
}
quikSort(a, 0, n-1,K);
return a[n-K];
}
void quikSort(vector<int> &a,int left,int right,int k){
if(left > right || k <= 0){
return;
}
int i = left,j = right;
int base = a[left];
while(i < j){
while(a[j] > base && i < j){
j--;
}
while(a[i] <= base && i < j){
i++;
}
if(i < j){
swap(a[i], a[j]);
}
}
a[left] = a[i];
a[i] = base;
int len = right - i;
if(len > k-1){
quikSort(a, i+1, right,k);
}else if(len < k-1){
quikSort(a, left, i-1,k-len-1);
}
}
};
查看10道真题和解析
投递美团等公司10个岗位