215. 数组中的第K个最大元素(medium)

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

• show the code:

class Solution(object):  
    def partition(self,a,lo,hi):
        pivot = a[lo]# 选取第一个为枢轴值
        while lo < hi:
            while lo < hi and a[hi] <= pivot:
                hi -= 1
            a[lo] = a[hi]
            while lo < hi and a[lo] >= pivot:
                lo += 1
            a[hi] = a[lo]
        a[lo] = pivot
        return lo
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.quicksort(nums,0,len(nums)-1,k)
    def quicksort(self,nums,begin,end,k):
        if begin >= end:
            return nums[begin]
        mid = self.partition(nums,begin,end)
        if mid == k-1:
            return nums[mid]
        elif mid > k-1:
            return self.quicksort(nums,0,mid-1,k)
        else:
            return self.quicksort(nums,mid+1,end,k)

• 此题的重点是写出partition函数，由于是选出topk大的数，我们partition函数作用就是将比临界值大的数分在其左边，比临界值小的数分在右边。因此我们利用双指针，从左边右边分别开始循环，这里需要注意：如果我们选择第一个数作为临界值，那么就要从右边开始寻找“异常值”（比临界值大的值）如果我们选择最后一个数作为临界值，那么就要从左边开始寻找“异常值”。
• 然后利用两步赋值完成交换，最后在双指针碰撞时，将临界值插入数组中，返回临界值的索引。
• 写出partition函数后就好做了，每一次partition后都能把一个数放到其正确排序位置上，可以不断缩小寻找范围。
• 时间复杂度介于之间，一般可以达到。