[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)。我们不需要任何额外空间，代码如下：