立如芝兰玉树
笑如朗月入怀
很多人是直接排序的2333。还是那句话，希望这样的老哥多一点，这样我在找工作的时候会轻松一点。
面试的时候经常被问到topK的问题，topK就能够用快排的partition来解，这道题也是内味。
每次调用partition，都能确定出整个数组中某个元素的位置。。。根据这个功能，就可以递归地缩小范围，直到某次调用partition时确定的某个元素的下标正好是第(K + 1) / (N - K)个。
快排3年前难写出来是因为递归不好理解，现在难写出来是发现这个partition怎么写都不对。。。
索性花了几周把这个partition给背下来了，唉。。。
class Solution {
private:
int partition(vector<int> &nums, int left, int right) {
int len = right - left + 1;
int pivot = rand() % len + left;
swap(nums[pivot], nums[left]);
int L = left;
while (left < right) {
while (left < right && nums[right] > nums[L]) right--;
while (left < right && nums[left] <= nums[L]) left++;
if (left < right)
swap(nums[left], nums[right]);
}
swap(nums[left], nums[L]);
return left;
}
int quicksort(vector<int> &nums, int left, int right, const int k) {
int pivot = partition(nums, left, right);
if (pivot + k == nums.size())
return nums[pivot];
if (pivot + k < nums.size())
return quicksort(nums, pivot + 1, right, k);
else return quicksort(nums, left, pivot - 1, k);
}
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
return quicksort(nums, 0, nums.size() - 1, k);
}
};
