题目

在未排序的数组中找到第 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） 链接：LeetCode215. 数组中的第K个最大元素 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一 (暴力排序法)

思路 因为python是用list代替数组的，所以可以直接利用python提供的list.sort()函数对其进行排序后取对应大小的数代码 class Solution(object): def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ nums.sort() return nums[-k] 结果

解法二(堆排序)

思路 建立一个大小不超过k的小根堆，其根节点即为所求代码 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: #利用自带库函数，一行解决 #return heapq.nlargest(k, nums)[-1] myheap=[] for num in nums: self.AddtoHeap(myheap,num) if len(myheap)>k: #若堆的大小超过k，直接移除当前的根节点 myheap.pop(0) return myheap[0] def AddtoHeap(self,heap,num): lens,i=len(heap),0 heap.insert(0,num) #将新元素直接插入根节点位置 while i<=lens//2: #调整堆 if i*2+1<=lens and heap[i*2+1]<heap[i*2]: m=i*2+1 else: m=i*2 if heap[m]<heap[i]: temp=heap[m] heap[m],heap[i]=heap[i],temp i=m else: break 结果