LeetCode215.数组中的第K大元素-蟒蛇

215。TheKthLargestElementinanArray题目来源：LeetCodehttps://leetcode-cn.com/problems/kth-largest-element-in-an-array题目目标在未排序的数组中找到第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大的元素，然后建立一个最大堆实现堆序，进行k-1次删除操作后，堆顶的元素就是答案。在Python中，也有对应的API，可以直接使用。这里，堆是单独实现的，没有借助API。具体算法设计（简单步骤如下）：首先构建最大堆，将数组元素存储在二叉树中，构建完备二叉树；实现堆的顺序；删除第k-1个根节点（堆顶元素），注意恢复堆性的顺序。以例1为例：输入：[3,2,1,5,6,4]andk=2输出：5具体过程见下图（以例1为例）：具体实现代码如下。代码实现fromtypingimportListclassSolution:deffindKthLargest(self,nums:List[int],k:int)->int:heap_size=len(nums)self.build_max_heap(nums,heap_size)foriinrange(len(nums))-1,len(nums)-k,-1):nums[0],nums[i]=nums[i],nums[0]heap_size-=1self.max_heapify(nums,0,heap_size)返回nums[0]defbuild_max_heap(self,nums,heap_size):foriinrange(heap_size//2,-1,-1):self.max_heapify(nums,i,heap_size)defmax_heapify(self,nums,i,heap_size):left=i*2+1right=i*2+2largest=iifleftnums[largest]:largest=leftifrightnums[largest]:largest=rightif(largest!=i):nums[i],nums[largest]=nums[largest],nums[i]self.max_heapify(nums,largest,heap_size)实际结果总结该题需要第k大元素，所以可以建一个最大堆，实现堆排序，删除k-1个元素（恢复堆序）。这时候堆顶元素就是答案。这里不使用api，尝试自己实现堆。具体算法如下：构建最大堆，将数组元素存放在堆中，构建一棵完全二叉树，实现堆的有序化；删除k-1个元素（注意恢复堆的顺序），此时堆顶就是要求的答案。文字原创，欢迎关注点赞。微信公众号《书所集录》同步更新，也欢迎大家关注。