【牛客题霸每日一题】NC88 寻找第K大 题解
快速排序每次在 l, r 范围内递归地进行元素排序，加入参数 k ，使得快速排序每次只在递归的一侧进行，代码如下：
class Finder {
public:
int partition(vector<int>& arr, int left, int right) {
int pivot = left;
int lt = left + 1;
int gt = right;
while (true) {
while (lt <= right && arr[lt] < arr[pivot]) lt++;
while (gt >= left && arr[gt] > arr[pivot]) gt--;
if (lt > gt) break;
swap(arr[lt], arr[gt]);
lt++;
gt--;
}
swap(arr[pivot], arr[gt]);
return gt;
}
int findKth(vector<int> arr, int n, int k) {
// write code here
k = n - k;
int left = 0, right = arr.size() -1;
int pivot = 0;
do {
pivot = partition(arr, left, right);
if(pivot == k){
break;
}else if(pivot > k){
right = pivot - 1;
}else {
left = pivot + 1;
}
}while(true);
return arr[pivot];
}
};
查看26道真题和解析
