https://leetcode.cn/problems/kth-largest-element-in-an-array/
solution1:
使用min-heap,找第k大的元素
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # python默认是小顶堆 hq = nums[:k] heapq.heapify(hq) for i in range(k, len(nums)): if nums[i] > hq[0]: heapq.heappop(hq) heapq.heappush(hq, nums[i]) return hq[0]View Code
solution2:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
import random def findKthLargest(self, nums: List[int], k: int) -> int: def partition(nums, left, right): # 1.generating a random number between the starting index of the array # and the ending index of the array p = random.randint(left, right) # 2.swapping ending element of the array and the pivot nums[p], nums[right] = nums[right], nums[p] pivot = nums[right] # 3. [0...pos) 存储小于pivot的元素 pos = left for i in range(left, right): if nums[i] < pivot: nums[pos], nums[i] = nums[i], nums[pos] pos += 1 nums[right], nums[pos] = nums[pos], nums[right] return pos n = len(nums) left, right = 0, n - 1 while left <= right: pos = partition(nums, left, right) if pos == n - k: break elif pos < n - k: left = pos + 1 else: right = pos - 1 return nums[pos]View Code
标签:right,nums,int,hq,pos,Element,Kth,Largest,left From: https://www.cnblogs.com/zijidan/p/16882827.html