跳转至

215. 数组中的第K个最大元素

LeetCode 2151 · 中等 · 堆

题

给一个整数数组和 k，返回排序后第 k 大的元素（按位置算，重复值各占一位，不是第 k 个不同的值）。要求期望时间优于排序。

例：nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 → 4。

一句话

维护一个只装 k 个元素的小顶堆，堆顶就是「目前第 k 大」；或者用快速选择，只递归包含第 k 大的那一侧。

关键技巧

小顶堆找第 k 大——反直觉但对。 堆里始终保留见过的最大的 k 个数，堆顶是这 k 个里最小的，也就是第 k 大。新数 x 比堆顶大就替换堆顶，否则丢弃。不变量：扫完前缀后，堆 = 前缀里最大的 k 个。\(O(n \log k)\)，适合数据流、k 远小于 n。

快速选择 = 只走一边的快排。 按 pivot 划分后，pivot 的最终位置确定了；目标下标在哪边就只处理哪边。期望规模每次减半：\(n + n/2 + n/4 + \cdots = O(n)\)。

两个退化点必须防住：

  • 有序输入：固定选首元素当 pivot，每次只切掉一个，\(O(n^2)\)——随机选 pivot。
  • 大量重复值（如全相同）：二路划分会把相等元素都丢到一边，同样 \(O(n^2)\)——用三路划分，把数组分成 > pivot | == pivot | < pivot，目标落在中段直接返回。

解

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        while True:
            pivot = random.choice(nums)
            big = [x for x in nums if x > pivot]
            eq = [x for x in nums if x == pivot]
            if k <= len(big):
                nums = big                   # 第 k 大在「更大」那一段
            elif k <= len(big) + len(eq):
                return pivot                 # 落在等于 pivot 的中段
            else:
                k -= len(big) + len(eq)
                nums = [x for x in nums if x < pivot]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = nums[:k]
        heapq.heapify(heap)
        for x in nums[k:]:
            if x > heap[0]:              # 比当前第 k 大还大，替换进来
                heapq.heapreplace(heap, x)
        return heap[0]

快速选择：期望时间 \(O(n)\)，空间 \(O(n)\)（这里为了清晰用了新列表；原地划分可做到 \(O(1)\)）。小顶堆：时间 \(O(n \log k)\)，空间 \(O(k)\)。

延伸

自测 
s = Solution()
assert s.findKthLargest([3, 2, 1, 5, 6, 4], 2) == 5
assert s.findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert s.findKthLargest([1], 1) == 1
assert s.findKthLargest([7] * 1000, 500) == 7          # 全重复
assert s.findKthLargest(list(range(10000)), 1) == 9999  # 有序输入

  1. LeetCode 215，2026-09-29 读。 ↩