带中位数写法的快速排序再讨论 & 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];
	}
};

这里展示的是这道题的通过代码，不过本质上和放排序代码一样，偷个懒