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

题目链接（中等）

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

数据范围：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

示例

示例 1：

输入： nums = [3,2,1,5,6,4], k = 2
输出： 5

示例 2：

输入： nums = [3,2,3,1,2,4,5,5,6], k = 4
输出： 4

核心思路

本题最直接的解法是排序后取倒数第 k 个，时间 $O(n \log n)$。但题目要求 $O(n)$，需要更快的做法。

两种主流思路：

1. 快速选择：基于快排的 partition 思想，每轮只递归一侧，平均时间 $O(n)$；
2. 堆：用小根堆维护前 k 大的元素，或大根堆做 k-1 次删除。

快速选择是本题的标准解法，因为它平均时间 $O(n)$，且不需要额外空间（原地修改）。

---

方法一：快速选择（Quick Select）

思路及解法

快速排序的 partition 过程：选一个主元 pivot，把数组重排成 [≤pivot, pivot, ≥pivot]，pivot 最终落在下标 q 上。

关键观察：partition 之后，a[q] 的位置已经确定——它就是整个数组排序后第 q 个位置的值。所以：

• 若 q == 目标下标，直接返回 a[q]；
• 若 q < 目标下标，说明答案在右半部分，只递归右半；
• 若 q > 目标下标，答案在左半部分，只递归左半。

每次只递归一侧，这就是「快速选择」比快排快的原因。

目标下标：题目要第 k 大，等价于从小到大排序后第 n - k 个下标（0-indexed）。

代码中的 partition 写法（双指针法，参考《算法导论》）：

• 主元 pivot = nums[l]；
• i = l - 1，j = r + 1；
• 循环：i 向右找第一个 ≥ pivot 的，j 向左找第一个 ≤ pivot 的；
• 若 i < j，交换，继续；
• 否则结束，j 就是分界点。

为什么不用三路或随机：本题官方解法用的是双指针 partition，对多数数据表现良好。如果担心最坏情况 $O(n^2)$，可以在 partition 前随机选一个主元和 nums[l] 交换。

代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickselect(l: int, r: int, k: int) -> int:
            if l == r:
                return nums[k]
            pivot_idx = random.randint(l, r)
            nums[l], nums[pivot_idx] = nums[pivot_idx], nums[l]
            partition = nums[l]
            i, j = l - 1, r + 1
            
            while i < j:
                i += 1
                while nums[i] < partition:
                    i += 1
                j -= 1
                while nums[j] > partition:
                    j -= 1
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            
            if k <= j:
                return quickselect(l, j, k)
            else:
                return quickselect(j + 1, r, k)
        
        n = len(nums)
        return quickselect(0, n - 1, n - k)

复杂度分析

• 时间复杂度：平均 $O(n)$，最坏 $O(n^2)$（可用随机主元降低概率）。
• 空间复杂度：$O(\log n)$，递归栈的期望深度。

---

方法二：小根堆（维护前 k 大）

思路及解法

换一种视角：题目求第 k 大，等价于「维护一个大小为 k 的最小堆，堆顶就是第 k 大」。

流程：

1. 遍历数组，把元素依次加入小根堆；
2. 堆大小超过 k 时，弹出堆顶（当前 k+1 个元素里最小的）；
3. 遍历结束后，堆里留下的就是最大的 k 个元素；
4. 堆顶（最小值）就是第 k 大。

为什么堆顶是第 k 大？

堆里始终保留「已经遍历过的元素中最大的 k 个」。遍历完全部元素后，堆里就是整个数组最大的 k 个，堆顶是其中最小的，即第 k 大。

Python 的 heapq 是小根堆，直接用即可。

代码

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

也可以先用 heapq.nlargest(k, nums)，再取最小值，效果一样。

复杂度分析

• 时间复杂度：$O(n \log k)$，每个元素入堆 / 出堆 $O(\log k)$。
• 空间复杂度：$O(k)$，堆最多存 k 个元素。

---

方法三：手写大根堆（面试加分）

思路及解法

面试时面试官可能要求手写堆，不允许用库。

大根堆思路：

1. 把整个数组建成大根堆（buildMaxHeap）；
2. 做 k-1 次「删除堆顶」（把堆顶和末尾交换，堆大小减 1，再调整）；
3. 此时堆顶就是第 k 大。

三个核心函数：

• maxHeapify(a, i, size)：调整节点 i 使其满足大根堆性质，递归下沉；
• buildMaxHeap(a, size)：从最后一个非叶节点开始，依次 maxHeapify；
• 删除堆顶：把堆顶与末尾交换，size -= 1，对堆顶再做一次 maxHeapify。

代码

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        def max_heapify(a: list[int], i: int, size: int) -> None:
            """调整节点 i，使其满足大根堆性质"""
            l, r = 2 * i + 1, 2 * i + 2
            largest = i
            if l < size and a[l] > a[largest]:
                largest = l
            if r < size and a[r] > a[largest]:
                largest = r
            if largest != i:
                a[i], a[largest] = a[largest], a[i]
                max_heapify(a, largest, size)

        def build_max_heap(a: list[int]) -> None:
            """从最后一个非叶节点开始建堆"""
            n = len(a)
            for i in range(n // 2 - 1, -1, -1):
                max_heapify(a, i, n)

        n = len(nums)
        build_max_heap(nums)

        # 删除堆顶 k-1 次
        heap_size = n
        for _ in range(k - 1):
            nums[0], nums[heap_size - 1] = nums[heap_size - 1], nums[0]
            heap_size -= 1
            max_heapify(nums, 0, heap_size)

        return nums[0]

复杂度分析

• 时间复杂度：$O(n + k \log n)$，建堆 $O(n)$，每次删除 $O(\log n)$，共 k-1 次。最坏是 $O(n \log n)$。
• 空间复杂度：$O(\log n)$，max_heapify 递归的栈空间。

---

三种方法对比

方法	时间（平均）	时间（最坏）	空间	特点
快速选择	$O(n)$	$O(n^2)$	$O(\log n)$	平均最快，原地修改，面试首选
小根堆	$O(n \log k)$	$O(n \log k)$	$O(k)$	稳定，适合求「前 k 大」的场景
手写大根堆	$O(n \log n)$	$O(n \log n)$	$O(\log n)$	考察堆的实现细节

推荐：

• 面试：首选快速选择，因为它是本题唯一能达到 $O(n)$ 的方法；
• 不想写递归：用小根堆，代码最短，$O(n \log k)$ 也能接受；
• 考察堆实现：用手写大根堆，展示对数据结构的掌握。

---

关键细节

1. 目标下标是 n - k

题目求第 k 大，如果按从小到大排序，它在第 n - k 个位置（0-indexed）。

例如 nums = [1,2,3,4,5]，k = 2（第 2 大）：

• 从小到大排序：[1,2,3,4,5]；
• 第 2 大是 4，下标为 3 = n - k = 5 - 2。

2. 快速选择的递归方向

if k <= j:
    return quickselect(l, j, k)
else:
    return quickselect(j + 1, r, k)

• j 是分界点，nums[j] 是主元所在位置；
• 若目标 k 在 [l, j] 里，只递归左边；
• 否则在 [j+1, r] 里，只递归右边。

每次只走一侧，所以平均时间 $O(n)$。

3. 快排 partition 的双指针写法

i, j = l - 1, r + 1
while i < j:
    i += 1
    while nums[i] < pivot:
        i += 1
    j -= 1
    while nums[j] > pivot:
        j -= 1
    if i < j:
        nums[i], nums[j] = nums[j], nums[i]

这个写法把主元 pivot 单独存在变量里，避免了多次比较。循环结束时 j 是分界点。

4. 堆方法为什么用「小根堆」而不是「大根堆」

• 小根堆：堆里维持 k 个元素，堆顶是其中最小的，即第 k 大 —— 直接；
• 大根堆：需要把所有元素建堆，再删 k-1 次才能拿到第 k 大 —— 间接。

从效率上，小根堆 $O(n \log k)$ 优于大根堆 $O(n \log n)$（当 k 远小于 n 时）。

5. 快速选择的最坏情况

如果每次选的主元都是最大或最小元素，递归只减少一个元素，退化成 $O(n^2)$。

规避方法：

• 随机选主元（random.randint(l, r) 交换到首位）；
• 或者用「三数取中」选主元。

本题数据一般不会刻意卡，但加上随机化更保险。

---

总结

• 本质：找数组从小到大第 n - k 个元素；
• 快速选择：partition 后判断目标在左侧还是右侧，只递归一侧，平均 $O(n)$；
• 小根堆：维护大小为 k 的最小堆，遍历结束后堆顶即答案，$O(n \log k)$；
• 手写大根堆：建堆 + k-1 次删除，考察堆的三个核心操作；
• 通用套路：「求第 k 大 / 第 k 小」问题的三种武器——快选、堆、排序。

相关题目

• LC 347. 前 K 个高频元素（堆 + 哈希）
• LC 703. 数据流中的第 K 大元素（维护固定大小的小根堆）
• LC 973. 最接近原点的 K 个点（快速选择 / 堆）
• LC 4. 寻找两个正序数组的中位数（二分 + 划分）