[LeetCode]Kth Largest Element in an Array

用Quick Select可以解的题目。Quick Select只用Quick Sort的Partition阶段，也就是我们随机选取一个数（实现的时候我们选当前区间的第一个数），然后用这个数x将区间二分。这一题因为要我们找第k大的数，所有>=x的数在左边，所有<=x的数在右边。然后根据k的值，我们决定去左边还是右边继续寻找。时间复杂度worst case是O(n^2)，因为可能输入数组本身就是有序的，我们每次partition就会一半是0个数，一半是剩下的数，也就是我们只能去掉一个数（用来partition的数）。假设我们要找最小的数，那么时间复杂度就为O(n^2)。但是如果每次run quick select之前可以shuffle的话，让我们每次二分可以分两个size相近的区间，这里我们不做严格的证明，我们会有T(n) = T(n/2) + n，展开之后T(n) = n + n / 2 + n / 4 + ... + 1 = O(n)。我们不需要任何额外空间，代码如下：

	class Solution {
	public:
	int findKthLargest(vector<int>& nums, int k) {
	return quickSelect(nums, 0, nums.size() - 1, k);
	}
	private:
	int quickSelect(vector<int>& nums, int lo, int hi, int k)
	{
	if(lo == hi)return nums[lo];
	int num = nums[lo], i = lo + 1, j = hi;
	while(true)
	{
	while(i <= hi && nums[i] >= num)++i;
	while(j > lo && nums[j] <= num)--j;
	if(i > j)break;
	swap(nums[i], nums[j]);
	}
	swap(nums[lo], nums[j]);
	if(k == j + 1 - lo)return nums[j];
	else if(k < j + 1 - lo)return quickSelect(nums, lo, j - 1, k);
	else return quickSelect(nums, j + 1, hi, k - (j + 1 - lo));
	}
	};

view raw Kth Largest Element in an Array.cpp hosted with ❤ by GitHub