https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1018/
在未排序的数组中找到第 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 ≤ 数组的长度。
数组中的第K个最大元素，这个题难度比较适中，可以检验下自己排序的基础知识是否扎实。
比较好的思路：借鉴快速排序，快速排序是选一个pos，然后比pos小的交换到左边，pos大的交换到右边
交换一轮后就可以找到pos是k_pos几大的元素（注意第几大是指倒序排序！）。
每次快排完成后，有3种情况：
- k_pos == target：恭喜直接返回pos
- k_pos>target： k_pos是指数组中第k_pos的数，比如pos是第10大的数，但是我要找target是第5大的数，说明要找的数还在我的右边，同时target不用变。
- k_pos<target： 例如pos是第10大的数，我要找第15大的数，说明得在pos的左边继续找，而且只需要找第5大的数就好啦
代码如下：
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if not nums:
return None
left = 0
right = len(nums) - 1
while left <= right:
pos = self.quicksort(nums, left, right)
k_sort = right-pos+1 # 比pos大的数字个数，比如pos是第k_sort大的数
if k_sort == k:
return nums[pos]
elif k_sort > k:
# 比pos大的个数k，说明还需要右边继续找
left = pos + 1
else:
k = k - k_sort
right = pos - 1
return None
def quicksort(self, nums, left, right):
pos = nums[left]
start = left
while left != right:
while (nums[right] >= pos and left < right):
right -= 1
while (nums[left] <= pos and left < right):
left += 1
if left != right:
nums[left], nums[right] = nums[right], nums[left]
else:
nums[left], nums[start] = nums[start], nums[left]
return left
第二个思路也很直接，构建一个长度为K的小跟堆（注意是小跟堆！）
然后堆顶其实就是第K大的数，循环这个数组，迭代这个小跟堆，最后返回堆顶元素就好了。这个思路比较考验手写堆排序，堆排序值得注意的一点是，根节点为i，左节点为i2+1,右节点坐标为i2+2。在调整堆的遍历中，是要满足左节点在范围内既要遍历，所以是i*2+1<=end。具体代码如下：
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if not nums:
return None
if len(nums) ==1 and k==1:
return nums[0]
heap_nums = []
for i in range(0,k):
heap_nums.append(nums[i])
# 建立K的小跟堆
for i in range(k/2-1,-1,-1):
self.adjustHeap(heap_nums,i,k-1)
# 遍历数组，找到第K大的数字，如果发现元素比堆顶大，则要更新堆了
for i in range(k,len(nums)):
if nums[i] > heap_nums[0]:
heap_nums[0] = nums[i]
self.adjustHeap(heap_nums,0,k-1)
return heap_nums[0]
def adjustHeap(self,heap_nums,start,end):
pos = start
while pos <= (end-1)/2:
min_child_pos = pos*2+1 # 默认设置为left值
# 找到左右节点中最小的节点
right_child_pos = pos*2 +2
if right_child_pos <= end:
if heap_nums[min_child_pos]>heap_nums[right_child_pos]:
min_child_pos = right_child_pos
if heap_nums[pos]>heap_nums[min_child_pos]:
heap_nums[pos],heap_nums[min_child_pos] = heap_nums[min_child_pos],heap_nums[pos]
pos = min_child_pos
else:
break
return
