TopK问题有两种常见的解决方式，一种是利用堆，一种是利用快速排序的partition过程。
一，堆
import heapq class Finder: def findKth(self, a, n, K): b = list(map(lambda x:-x, a)) heapq.heapify(b) for _ in range(K-1): heapq.heappop(b) return -heapq.heappop(b)二，随机快排
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: len_nums = len(nums) def partition(nums, low, high, pivot): l = low - 1 r = high + 1 h = low while h < r: if nums[h] < pivot: l += 1 nums[h], nums[l] = nums[l], nums[h] h += 1 elif nums[h] == pivot: h += 1 else: r -= 1 nums[h], nums[r] = nums[r], nums[h] return l+1, r-1 low = 0 high = len_nums-1 while low <= high: pivot = random.randint(low, high) pi_l, pi_r = partition(nums, low, high, nums[pivot]) if pi_l <= len_nums - k <= pi_r: return nums[pi_l] elif pi_l > len_nums - k: high = pi_l - 1 elif pi_r < len_nums - k: low = pi_r + 1
