LeetCode 215. 数组中的第K个最大元素 题目描述 给定一个整数数组 nums 和一个整数 k ，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1: 输入: [ 3,2,1,5,6,4 ], k = 2 输出: 5 解释：排序后数组是 [ 1,2,3,4,5,6 ]，第2个最大的元素是5。 示例 2: 输入: [ 3,2,3,1,2,4,5,5,6 ], k = 4 输出: 4 解释：排序后数组是 [ 1,2,2,3,3,4,5,5,6 ]，第4个最大的元素是4。 解题过程 我们的目标是找到数组中第 k 大的数。最直观的方法是先将整个数组排序，然后直接通过索引访问第 k 大的元素。例如，在一个长度为 n 的升序数组中，第 k 大的元素就是 nums[n-k] 。这种方法的时间复杂度是 O(n log n)，主要由排序决定。 然而，我们是否真的需要对所有 n 个元素进行完全排序才能得到答案呢？其实不必。我们只需要找到那个特定的元素，而不关心其他元素之间的相对顺序。这引导我们使用一种更高效的思路： 分治选择算法 ，或者使用 堆（优先队列） 。 下面，我将详细讲解基于 最小堆 的解法，因为它既高效又易于理解。 步骤 1：理解核心思路 想象我们有一个容量为 k 的"篮子"。我们的目标是让这个篮子里始终装着当前看到的、最大的 k 个数。因为篮子容量有限，我们只关心最小的那个数会不会被更大的数替换掉。如果这个篮子里装的是最大的 k 个数，那么篮子里最小的那个数，不就是整个数组中第 k 大的数吗？ 这个"篮子"就是我们要维护的一个 最小堆 。堆顶（根节点）是这个堆里最小的元素。 步骤 2：算法流程 初始化： 创建一个最小堆。我们先取数组中的前 k 个元素放入堆中。 此时，堆里装的就是我们当前看到的全部数字（前 k 个）中最大的 k 个（因为只有这 k 个）。堆顶是这 k 个数里最小的。 遍历剩余元素： 从第 k+1 个元素开始，遍历数组中剩下的所有元素。 对于当前遍历到的数字 num ，我们将其与堆顶元素进行比较。 关键判断： 如果 num 大于堆顶元素，说明 num 有资格进入"最大的 k 个数"这个俱乐部。而为了维持俱乐部只有 k 个成员，我们就必须把当前俱乐部里最小的那个（即堆顶）踢出去。 操作： 先将当前的堆顶元素弹出（移除），然后将 num 加入堆中。 如果 num 小于或等于堆顶元素，说明它比我们俱乐部里最差的成员还要差，它没有资格进入，我们直接忽略它。 返回结果： 在遍历完整个数组之后，我们的最小堆里存放的就是整个数组中最大的 k 个元素。由于这是最小堆，堆顶元素就是这个堆里最小的，也就是整个数组中第 k 大的元素。直接返回堆顶元素即可。 步骤 3：结合示例逐步推导 让我们用示例1来走一遍流程： nums = [3,2,1,5,6,4] , k = 2 初始化堆（容量k=2）： 将前2个元素 [3, 2] 加入最小堆。 堆会自动调整结构，堆顶是最小元素。此时堆为 [2, 3] （或类似结构，但堆顶一定是2）。 当前堆顶（第2大的候选）是 2 。 遍历剩余元素 [1, 5, 6, 4] ： 处理 num = 1 : 比较 1 和堆顶 2 。 1 <= 2 ，忽略。堆保持不变 [2, 3] ，堆顶为 2 。 处理 num = 5 : 比较 5 和堆顶 2 。 5 > 2 ，说明 5 更大。 操作： 弹出堆顶 2 ，加入 5 。 现在堆是 [3, 5] ，堆顶变为 3 。 处理 num = 6 : 比较 6 和堆顶 3 。 6 > 3 。 操作： 弹出堆顶 3 ，加入 6 。 现在堆是 [5, 6] ，堆顶变为 5 。 处理 num = 4 : 比较 4 和堆顶 5 。 4 <= 5 ，忽略。堆保持不变 [5, 6] ，堆顶为 5 。 返回结果： 遍历结束，堆顶元素是 5 。所以第2大的元素是 5 ，与预期一致。 步骤 4：复杂度分析 时间复杂度：O(n log k) 我们遍历了所有 n 个元素。 每次对堆的操作（插入或删除）时间复杂度是 O(log k)，因为堆的大小最多为 k 。 最坏情况下，每个元素都可能进行一次堆操作，所以总时间是 O(n log k)。 当 k 远小于 n 时，这比 O(n log n) 的全排序要快得多。 空间复杂度：O(k) 我们只需要维护一个大小为 k 的堆。 总结 通过维护一个大小为 k 的最小堆，我们巧妙地避免了完全排序，只关注于寻找最大的 k 个数的集合，并利用最小堆的性质快速找到这个集合中的最小值，即我们所求的第 k 个最大元素。这种方法在 k 较小的情况下非常高效。