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

2026-09-06 HGNULB 约 5 分钟

文章信息 33 个分类 6 个标签

分类

LeetCode CodeTop 中等已解决已掌握历史考题 500+ 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东华为拼多多网易小米商汤旷视亚马逊虾皮图森携程哔哩哔哩小红书作业帮 LeetCode 75 LeetCode 热题 100 面试经典 150 题

题目描述

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

题意分析

给定数组 nums 和整数 k，返回数组按降序排列后位于第 k 位的元素。

首先要把题意的一个坑钉死：这里的「第 k 大」是按出现次数排名，不是「第 k 个不同的值」。例如 [3,2,3,1,2,4,5,5,6] 中 k = 4 的答案是 4——降序为 6,5,5,4,...，两个 5 各占一个名次。所以绝对不能去重。

其次要注意题目只索取一个排名位置，并没有要求整个数组有序。直接排序再取下标是 $O(n \log n)$，能过但浪费了大量信息：第 k 位之后的元素之间的相对顺序对答案毫无影响。围绕这一点有两条优化路线。

第一条是只维护 k 个候选。如果手上始终只保留「已扫描元素中最大的 k 个」，扫完之后这批候选里最小的那个就是答案。维护这样一个集合、并能快速找出其中最小值，正是最小堆的职责，代价降到 $O(n \log k)$。

第二条是只递归目标所在的一侧。快速排序的分区操作能把基准值放到它的最终位置上，一次分区之后就能判断目标下标落在哪一侧，另一侧可以整块丢弃。这就是快速选择，平均 $O(n)$。

题目还有一句「请设计并实现时间复杂度为 $O(n)$ 的算法」，这句话是明确在点快速选择。面试中通常先给堆解法拿分，再补快速选择应对追问。

解法：三路分区快速选择

核心思路

第 k 大等价于升序数组下标 n - k。快速选择每轮只对目标所在区间继续分区，无需完整排序。

三路分区把区间划为 < pivot、== pivot、> pivot 三段。目标落在等值段时直接返回；大量重复值也能一次处理完。

解题步骤

计算目标下标 target = nums.length - k。

在当前区间进行升序三路分区，得到等值区间 [lt, gt]。

target < lt 时搜索左侧，target > gt 时搜索右侧，否则返回 nums[target]。

代码实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int pivot = nums[left + (right - left) / 2];
            int lt = left, i = left, gt = right;

            while (i <= gt) {
                if (nums[i] < pivot) {
                    swap(nums, lt++, i++);
                } else if (nums[i] > pivot) {
                    swap(nums, i, gt--);
                } else {
                    i++;
                }
            }

            if (target < lt) {
                right = lt - 1;
            } else if (target > gt) {
                left = gt + 1;
            } else {
                return nums[target];
            }
        }
        throw new IllegalStateException();
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func findKthLargest(nums []int, k int) int {
    target := len(nums) - k
    left, right := 0, len(nums)-1

    for left <= right {
        pivot := nums[left+(right-left)/2]
        lt, i, gt := left, left, right

        for i <= gt {
            if nums[i] < pivot {
                nums[lt], nums[i] = nums[i], nums[lt]
                lt++
                i++
            } else if nums[i] > pivot {
                nums[i], nums[gt] = nums[gt], nums[i]
                gt--
            } else {
                i++
            }
        }

        if target < lt {
            right = lt - 1
        } else if target > gt {
            left = gt + 1
        } else {
            return nums[target]
        }
    }
    panic("unreachable")
}

复杂度分析

时间复杂度：平均 $O(n)$，基准连续极端失衡时最坏 $O(n^2)$。

空间复杂度：$O(1)$，原地分区。

关键点总结

升序分区时目标下标是 n - k。

与右侧交换后不能移动 i，换来的元素尚未检查。

只处理目标所在的一侧；等值段可直接结束。

易错点总结

把第 k 大当成第 k 个不同元素，错误去重。

混用降序的 k - 1 与升序的 n - k。

三路分区边界写错，尤其是与 gt 交换后仍执行 i++。

忽略快速选择会修改原数组。

相似题目

题目	难度	考察点
347. 前 K 个高频元素	中等	先哈希计数再对「频次」求 Top K，也可用桶排序做到 $O(n)$
703. 数据流中的第 K 大元素	简单	流式场景，只有堆法适用，快速选择在此彻底失效
692. 前K个高频单词	中等	频次相同时按字典序，需要自定义比较器且注意堆的排序方向要取反
973. 最接近原点的 K 个点	中等	求第 K 小，改用最大堆；比较键换成距离平方，避免开方误差
912. 排序数组	中等	手写快排，本题分区逻辑的来源；同样需要三路分区应对重复值
378. 有序矩阵中第 K 小的元素	中等	借助行列有序，可用堆多路归并或对值域二分，Top K 的另一种解法
4. 寻找两个正序数组的中位数	困难	求第 k 小的进阶形态，需要在两个有序数组上二分划分
LCR 076. 数组中的第 K 个最大元素	中等	与本题同题，可直接套用
LCR 060. 前 K 个高频元素	中等	与 347 同题
剑指 Offer 40. 最小的k个数	简单	求最小的 k 个，堆的方向与本题相反，返回整批而非单个
面试题 17.14. 最小K个数	中等	与剑指 Offer 40 同题