力扣-0215.数组中的第K大元素【Python】

LeetCode0215.数组中的第K大元素【中】【Python】【快速排序】【堆】问题LeetCode在未排序的数组中找到第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≤数组的长度。问题在于Findthekthlargestelementinanunsortedarray。请注意，您正在寻找排序数组的第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个位置的元素。选择使用快速排序，即当分界点的索引为k-1时，为第k大的元素。具体可以参考耶鲁大学对QuickSelect算法的介绍。时间复杂度：O(n)空间复杂度：O(1)方法二：Heap构建最大堆，从上到下，第k个位置为第k大元素。时间复杂度：O(nlogk)空间复杂度：O(k)Python代码#方法1：快速排序类Solution(object):deffindKthLargest(self,nums,k):""":typenums:List[int]:输入k:int:rtype:int"""low,high=0,len(nums)-1whilelow<=high:pivot=self.partition(nums,low,high)ifpivot==k-1:#第k大，即第k-1位从大到小排序（从0开始计算）returnnums[pivot]ifpivot=pivot_value:nums[i],nums[index]=nums[index],nums[i]index+=1nums[index],nums[high]=nums[high],nums[index]returnindex#返回的索引就是分界点#方法二：HeapclassSolution(object):deffindKthLargest(self,nums,k):""":typenums:List[int]:typek:int:rtype:int"""#直接调用Python的heapq模块importheapqlist_k=heapq.nlargest(k,nums)returnlist_k.pop()题外话，Python自带的sorted()函数也可以用来排序。AReturnsorted(nums)[-k]#使用Python自带的排序算法。