题解 | #寻找第K大#
寻找第K大
https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
class Solution {
public:
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
int _qS(vector<int> &arr, int l, int r) {
swap(arr[l], arr[(l+r)/2]); // 选区间中间的点，避免极端情况导致时间复杂度达到n2
int temp = arr[l];
while(l < r) {
while(l < r && arr[r] >= temp) --r;
arr[l] = arr[r];
while(l < r && arr[l] <= temp) ++l;
arr[r] = arr[l];
}
arr[l] = temp;
return l;
}
void qS(vector<int> &arr, int l, int r, int target) {
if(l < r) {
int mid = _qS(arr, l, r);
if(mid == target) return;
else if(mid > target) qS(arr, l, mid, target); //只往一个方向递归
else qS(arr, mid+1, r, target);
}
}
int findKth(vector<int> a, int n, int K) {
// write code here
if(n == 0) return -1;
qS(a, 0, n-1, n-K);
return a[n-K];
}
};
题目意思很好理解，快排也好理解，有两个关键的问题。
第一个是找到mid之后通过比较和K的大小关系，只往一个方向递归快排；
第二个是快排的过程中为了避免极端情况，选取中间点的时候不要选最左边那个点，选个中间点之类的，要不会超时。
