描述
在未排序的数组中找到第 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链接
https://leetcode-cn.com/problems/kth-largest-element-in-an-array
思路
使用类似快排的思想：
1、随机选择一个数字后，分解成排序的2部分，返回随机数所在位置
2、根据随机数所在位置，循环分区，直到成功获取。
import random
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
left = 0
right = len(nums) -1
k = k-1
pos = self.partion(nums, k, left, right)
while pos != k:
if pos > k:
right = pos
pos = self.partion(nums, k, left, right-1)
elif pos < k:
left = pos
pos = self.partion(nums, k-(left+1), left+1, right)
return nums[k]
def partion(self, a, k, left, right):
"""
降序排列
"""
pos = random.randint(left, right)
a[pos], a[right] = a[right], a[pos]
i, j = left, left
while j < right:
if a[j] >= a[right]:
a[i], a[j] = a[j], a[i]
i = i + 1
j = j + 1
a[i], a[right] = a[right], a[i]
return i
