前言
吸烟有害健康，切记。最近要抓紧练车，考完驾照。今天大扫除，有点烦躁，不过寝室干净了，也是有点舒坦的。开始解题吧！回头加一句，一篇博客都写完了，还没回我。o(╥﹏╥)o
题目
在未排序的数组中找到第 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 ≤ 数组的长度。
思路
对于这个问题，可以说思路是比较清晰的，不过就是对这个数组进行排序而，然后输出对应下标的元素就行，不过我们还是要追求时间复杂度与空间复杂度尽可能的小。一开始我尝试着写了一个快排进行解决，不过不得不说，leetcode的测试用例也是蛮好，毕竟我们能想到的别人也能想到，快排的效率让我诧异，2016ms，只能说测试用例可能都是快排的最坏情况了。
不过这样才有改进的空间嘛！这个时候我想到一个结构————堆.小顶堆完美契合这道题。首先将数组中前k个数构造一个节点数为k的小顶堆，然后剩余的数与根节点进行比较，再下沉调整，最后将根节点输出即可。代码如下：
代码
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
self.build_heap(nums,k)
# print("小顶堆构造完毕")
for i in range(k,len(nums)):
if nums[i] > nums[0]:
nums[0] = nums[i]
self.maintain(nums,0,k)
return nums[0]
def maintain(self,List, index, length):
# print("父节点位置:",index,"父节点：",List[index])
temp = List[index]
childindex = 2 * index + 1
# print("左子节点 :",childindex)
while childindex < length:
if (childindex + 1 < length ) and (List[childindex + 1] < List[childindex]): #判断左右子节点的大小
childindex = childindex + 1
# print("右节点小")
if temp <= List[childindex]:
break
# print("位置：",childindex,"子节点 ",List[childindex])
List[index] = List[childindex]
index = childindex
childindex = 2*childindex+1
# print('节点下沉',List)
List[index] = temp
def build_heap(self,list,length):
i = int((length-2)/2) # 深度
while i>=0 :
self.maintain(list,i,length)
i -= 1
堆的执行过程：
数组为： [7, 9, 4, 2, 5, 1, 3, 6, 8, -1]
构建小顶堆
第2层
父节点的数组下标: 2 父节点值： 4
左子节点的数组下标 : 5
子节点的数组下标： 5 子节点值： 1
节点下沉 [7, 9, 1, 2, 5, 1, 3, 6, 8, -1]
下沉结束： [7, 9, 1, 2, 5, 4, 3, 6, 8, -1]
第1层
父节点的数组下标: 1 父节点值： 9
左子节点的数组下标 : 3
子节点的数组下标： 3 子节点值： 2
节点下沉 [7, 2, 1, 2, 5, 4, 3, 6, 8, -1]
下沉结束： [7, 2, 1, 9, 5, 4, 3, 6, 8, -1]
第0层
父节点的数组下标: 0 父节点值： 7
左子节点的数组下标 : 1
右节点小
子节点的数组下标： 2 子节点值： 1
节点下沉 [1, 2, 1, 9, 5, 4, 3, 6, 8, -1]
子节点的数组下标： 5 子节点值： 4
节点下沉 [1, 2, 4, 9, 5, 4, 3, 6, 8, -1]
下沉结束： [1, 2, 4, 9, 5, 7, 3, 6, 8, -1]
小顶堆构造完毕
比较其余数字
父节点的数组下标: 0 父节点值： 3
左子节点的数组下标 : 1
子节点的数组下标： 1 子节点值： 2
节点下沉 [2, 2, 4, 9, 5, 7, 3, 6, 8, -1]
右节点小
下沉结束： [2, 3, 4, 9, 5, 7, 3, 6, 8, -1]
父节点的数组下标: 0 父节点值： 6
左子节点的数组下标 : 1
子节点的数组下标： 1 子节点值： 3
节点下沉 [3, 3, 4, 9, 5, 7, 3, 6, 8, -1]
右节点小
子节点的数组下标： 4 子节点值： 5
节点下沉 [3, 5, 4, 9, 5, 7, 3, 6, 8, -1]
下沉结束： [3, 5, 4, 9, 6, 7, 3, 6, 8, -1]
父节点的数组下标: 0 父节点值： 8
左子节点的数组下标 : 1
右节点小
子节点的数组下标： 2 子节点值： 4
节点下沉 [4, 5, 4, 9, 6, 7, 3, 6, 8, -1]
子节点的数组下标： 5 子节点值： 7
节点下沉 [4, 5, 7, 9, 6, 7, 3, 6, 8, -1]
下沉结束： [4, 5, 7, 9, 6, 8, 3, 6, 8, -1]
第6大的数为：4
总结
在评论区看到一些人总结调用了python内置库的sort（）函数，说实话我蛮不屑这些拿内置函数来刷题的人，不过试了一下，真香。比堆排序快一点，那sort()函数的机制并不是用来一个快排这么简单，以前觉得sort()=快排，现在看来sort()还是一个优化过的快排，内部对不同情况进行不同的排序使用与它们的组合。我还只是个井底之蛙。不过你终于回我了。加油！！！
