带中位数写法的快速排序再讨论 & leetcode 215. Kth Largest Element in an Array题解
带中位数写法的快速排序再讨论 & leetcode 215. Kth Largest Element in an Array题解
探讨带中位数的写法本身
class Solution {
public:
int findKthLargest(std::vector<int>& nums, int k) {
return fakeQuickSort(nums, k, 0, nums.size() - 1);
}
private:
int fakeQuickSort(std::vector<int>& nums, int k, int l, int r) {
int x = find_pivot_down(nums, l, r);
int i = l, j = r;
while(i < j) {
do i++; while(nums[i] > x);
do j--; while(nums[j] < x);
if(i < j) std::swap(nums[i], nums[j]);
}
std::swap(nums[i], nums[r]);
if(r - l <= 2) {
return nums[l + k - 1];
}
int cnt = i - l + 1;
if(k < cnt) {
return fakeQuickSort(nums, k, l, i);
}
else {
return fakeQuickSort(nums, k - cnt, i + 1, r);
}
}
int find_pivot_up(std::vector<int>& nums, int l, int r) {
int mid = l + r + 1 >> 1;
if(nums[mid] < nums[l])
std::swap(nums[mid], nums[l]); // make sure nums[mid] >= nums[l]
if(nums[l] > nums[r])
std::swap(nums[l], nums[r]); // make sure nums[l] <= nums[r]
if(nums[mid] < nums[r])
std::swap(nums[mid], nums[r]); // make sure nums[mid] >= nums[r]
// nums[l] <= nums[r] <= nums[mid]
return nums[r];
}
int find_pivot_down(std::vector<int>& nums, int l, int r) {
int mid = l + r + 1 >> 1;
if(nums[l] < nums[mid])
std::swap(nums[l], nums[mid]); // make sure nums[l] >= nums[mid]
if(nums[l] < nums[r])
std::swap(nums[l], nums[r]); // make sure nums[l] >= nums[r]
if(nums[r] < nums[mid])
std::swap(nums[r], nums[mid]); // make sure nums[r] >= nums[mid]
// nums[mid] <= nums[r] <= nums[l]
return nums[r];
}
};这里展示的是这道题的通过代码，不过本质上和放排序代码一样，偷个懒