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

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1 2	>输入: [3,2,1,5,6,4], k = 2 >输出: 5

示例 2:

1 2	>输入: [3,2,3,1,2,4,5,5,6], k = 4 >输出: 4

主要使用归并排序

哨兵划分： 以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
递归： 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def quick_select(nums,k):
            pivot = random.choice(nums)
            big, equal, small = [], [], []
            for num in nums:
                if num > pivot:
                    big.append(num)
                elif num < pivot:
                    small.append(num)
                else:
                    equal.append(num)
            # 第K大的数字小于【大于基准数的所有数字】BIG的个数
            # 说明这个第K大的数字存在于这个数组BIG中，进入递归
            print(len(big) + 1 == len(nums)-len(small))
            if k <= len(big):
                return quick_select(big,k)
            # 第K大的数字存在SMALL中，进入递归
            # 此时len(small)+k>len(nums)
            # 问题也变成了寻找当前数组中第k - len(nums) + len(small)大的值
            if len(nums) - len(small) < k:
                return quick_select(small,k - len(nums) + len(small))
            return pivot
            
        return quick_select(nums,k)
```