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

LeetCode LeetCode 热题100 数组 排序 分治 快速选择 堆
发布时间 :
字数:2.8k 阅读 : 评论:
  1. 215.数组中的第K个最大元素
    1. 215.1 题目
    2. 215.2 题解
      1. 方法一：三路快速选择（QuickSelect，优化版）
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：小顶堆（优先队列）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 215.3 代码
    4. 215.4 运行结果

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

215.1 题目

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

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

示例 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

提示：

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

215.2 题解

方法一：三路快速选择（QuickSelect，优化版）

思路

快速选择的精髓：选一个 pivot，把数组分成「大于pivot」「等于pivot」「小于pivot」三部分，然后看 k 落在哪个区间。

三路分区的好处：如果 k 正好落在等于区，直接返回 pivot，不用继续递归。这对有大量重复元素的数组特别有效。

分区后：

  • k < lt：目标在大于区，递归左边
  • k > gt：目标在小于区，递归右边
  • 否则：k 在等于区，直接返回 pivot

举个例子：nums = [3,2,1,5,6,4], k = 2（找第2大）

  • 第1大的元素是6，第2大是5
  • 假设pivot=4，分区后：[5,6] [4] [3,2,1]
  • k=1落在大于区，递归[5,6]
  • 最终找到5

复杂度分析

  • 时间复杂度：平均 O(n)
  • 空间复杂度：O(1)

代码

// 静态Random，只实例化一次，保证随机数质量，避免短时间内重复new导致的伪随机
private static Random random = new Random();

// 方法一：三路快速选择（QuickSelect，优化版，平均时间复杂度 O(n)，专治海量重复元素）
// 核心思想：基于三路快排的分区思想，将数组分为「大于pivot」「等于pivot」「小于pivot」三部分
// 1. 若 k 落在「大于区」，递归搜索左半部分
// 2. 若 k 落在「等于区」，直接返回 pivot（无需递归，海量重复元素直接一步解决）
// 3. 若 k 落在「小于区」，递归搜索右半部分
static int FindKthLargestQuickSelect(int[] nums, int k)
{
    // 第 k 大的元素，对应从大到小排序后的索引 k-1
    return QuickSelect(nums, 0, nums.Length - 1, k - 1);
}

// 三路快速选择核心辅助函数
// nums：原始数组
// left：当前搜索范围的左边界
// right：当前搜索范围的右边界
// k：要找的第 k 大的元素的索引（从0开始）
static int QuickSelect(int[] nums, int left, int right, int k)
{
    // 递归终止条件：区间只有一个元素，直接返回
    if (left == right) return nums[left];

    // 随机选择 pivot，避免最坏情况（比如数组已排序）
    int pivotIndex = left + random.Next(right - left + 1);
    int pivot = nums[pivotIndex];

    // 三路分区核心：一次遍历将数组分为三部分
    // [left, lt)  ：大于 pivot 的区域
    // [lt, gt]    ：等于 pivot 的区域
    // (gt, right] ：小于 pivot 的区域
    int lt = left;  // 大于区的右边界（开区间）
    int gt = right; // 小于区的左边界（开区间）
    int i = left;   // 当前遍历指针

    while (i <= gt)
    {
        if (nums[i] > pivot)
        {
            // 当前元素大于 pivot，交换到大于区，扩大大于区
            Swap(nums, i, lt);
            lt++;
            i++;
        }
        else if (nums[i] < pivot)
        {
            // 当前元素小于 pivot，交换到小于区，扩大小于区
            // 注意：这里i不++，因为交换过来的元素还没处理
            Swap(nums, i, gt);
            gt--;
        }
        else
        {
            // 当前元素等于 pivot，直接留在等于区，继续遍历
            i++;
        }
    }

    // 根据 k 落在的区间，决定搜索方向
    if (k < lt)
    {
        // k 在大于区，递归搜索左半部分 [left, lt-1]
        return QuickSelect(nums, left, lt - 1, k);
    }
    else if (k > gt)
    {
        // k 在小于区，递归搜索右半部分 [gt+1, right]
        return QuickSelect(nums, gt + 1, right, k);
    }
    else
    {
        // k 在等于区，直接返回 pivot，无需递归！（海量重复元素的核心优化）
        return pivot;
    }
}

// 交换数组中两个元素的位置
static void Swap(int[] nums, int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

方法二：小顶堆（优先队列）

思路

维护一个大小为 k 的小顶堆，堆中存储当前最大的 k 个元素。

遍历数组，将每个元素加入堆。当堆大小超过 k 时，弹出堆顶（最小的元素），保证堆中始终是最大的 k 个元素。

遍历结束后，堆顶就是第 k 大的元素。

举个例子：nums = [3,2,1,5,6,4], k = 2

  • 加入3、2：堆=[2,3]
  • 加入1：堆=[1,2,3]，超过k=2，弹出1，堆=[2,3]
  • 加入5：堆=[2,3,5]，弹出2，堆=[3,5]
  • 加入6：堆=[3,5,6]，弹出3，堆=[5,6]
  • 加入4：堆=[4,5,6]，弹出4，堆=[5,6]
  • 堆顶5就是第2大的元素

复杂度分析

  • 时间复杂度：O(n log k)
  • 空间复杂度：O(k)

代码

// 方法二：小顶堆（优先队列，稳定版，时间复杂度 O(n log k)）
// 核心思想：维护一个大小为 k 的小顶堆，堆中存储当前最大的 k 个元素
// 1. 遍历数组，将元素加入堆
// 2. 当堆大小超过 k 时，弹出堆顶（最小的元素），保证堆中始终是当前最大的 k 个元素
// 3. 遍历结束后，堆顶就是第 k 大的元素
static int FindKthLargestHeap(int[] nums, int k)
{
    // C# 的 PriorityQueue 是最小堆，默认按优先级升序排列
    PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();

    foreach (int num in nums)
    {
        // 将当前元素加入堆，优先级为元素值本身
        minHeap.Enqueue(num, num);

        // 如果堆大小超过 k，弹出堆顶（最小的元素）
        if (minHeap.Count > k)
        {
            minHeap.Dequeue();
        }
    }

    // 堆顶就是第 k 大的元素
    return minHeap.Peek();
}

215.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
        // 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
        //
        // 示例 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
        //
        // 提示：
        // 1 <= k <= nums.length <= 10^5
        // -10^4 <= nums[i] <= 10^4

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 3, 2, 1, 5, 6, 4 };
        int k1 = 2;
        int result1 = FindKthLargestQuickSelect(CloneArray(nums1), k1);
        Console.WriteLine($"示例1 快速选择 方法 输入：{FormatArray(nums1)}, k={k1} 输出：{result1}");
        int result1_2 = FindKthLargestHeap(CloneArray(nums1), k1);
        Console.WriteLine($"示例1 小顶堆 方法 输入：{FormatArray(nums1)}, k={k1} 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 3, 2, 3, 1, 2, 4, 5, 5, 6 };
        int k2 = 4;
        int result2 = FindKthLargestQuickSelect(CloneArray(nums2), k2);
        Console.WriteLine($"示例2 快速选择 方法 输入：{FormatArray(nums2)}, k={k2} 输出：{result2}");
        int result2_2 = FindKthLargestHeap(CloneArray(nums2), k2);
        Console.WriteLine($"示例2 小顶堆 方法 输入：{FormatArray(nums2)}, k={k2} 输出：{result2_2}");

        #endregion
    }

    #region 辅助方法

    // 辅助方法：克隆数组，避免测试时修改原数组
    static int[] CloneArray(int[] nums)
    {
        if (nums == null) return null;
        return (int[])nums.Clone();
    }

    // 辅助方法：格式化数组为字符串，方便输出
    static string FormatArray(int[] nums)
    {
        if (nums == null || nums.Length == 0) return "[]";
        return $"[{string.Join(",", nums)}]";
    }

    #endregion

    #region 答案

    // 静态Random，只实例化一次，保证随机数质量，避免短时间内重复new导致的伪随机
    private static Random random = new Random();

    // 方法一：三路快速选择（QuickSelect，优化版，平均时间复杂度 O(n)，专治海量重复元素）
    // 核心思想：基于三路快排的分区思想，将数组分为「大于pivot」「等于pivot」「小于pivot」三部分
    // 1. 若 k 落在「大于区」，递归搜索左半部分
    // 2. 若 k 落在「等于区」，直接返回 pivot（无需递归，海量重复元素直接一步解决）
    // 3. 若 k 落在「小于区」，递归搜索右半部分
    static int FindKthLargestQuickSelect(int[] nums, int k)
    {
        // 第 k 大的元素，对应从大到小排序后的索引 k-1
        return QuickSelect(nums, 0, nums.Length - 1, k - 1);
    }

    // 三路快速选择核心辅助函数
    // nums：原始数组
    // left：当前搜索范围的左边界
    // right：当前搜索范围的右边界
    // k：要找的第 k 大的元素的索引（从0开始）
    static int QuickSelect(int[] nums, int left, int right, int k)
    {
        // 递归终止条件：区间只有一个元素，直接返回
        if (left == right) return nums[left];

        // 随机选择 pivot，避免最坏情况（比如数组已排序）
        int pivotIndex = left + random.Next(right - left + 1);
        int pivot = nums[pivotIndex];

        // 三路分区核心：一次遍历将数组分为三部分
        // [left, lt)  ：大于 pivot 的区域
        // [lt, gt]    ：等于 pivot 的区域
        // (gt, right] ：小于 pivot 的区域
        int lt = left;  // 大于区的右边界（开区间）
        int gt = right; // 小于区的左边界（开区间）
        int i = left;   // 当前遍历指针

        while (i <= gt)
        {
            if (nums[i] > pivot)
            {
                // 当前元素大于 pivot，交换到大于区，扩大大于区
                Swap(nums, i, lt);
                lt++;
                i++;
            }
            else if (nums[i] < pivot)
            {
                // 当前元素小于 pivot，交换到小于区，扩大小于区
                // 注意：这里i不++，因为交换过来的元素还没处理
                Swap(nums, i, gt);
                gt--;
            }
            else
            {
                // 当前元素等于 pivot，直接留在等于区，继续遍历
                i++;
            }
        }

        // 根据 k 落在的区间，决定搜索方向
        if (k < lt)
        {
            // k 在大于区，递归搜索左半部分 [left, lt-1]
            return QuickSelect(nums, left, lt - 1, k);
        }
        else if (k > gt)
        {
            // k 在小于区，递归搜索右半部分 [gt+1, right]
            return QuickSelect(nums, gt + 1, right, k);
        }
        else
        {
            // k 在等于区，直接返回 pivot，无需递归！（海量重复元素的核心优化）
            return pivot;
        }
    }

    // 交换数组中两个元素的位置
    static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 方法二：小顶堆（优先队列，稳定版，时间复杂度 O(n log k)）
    // 核心思想：维护一个大小为 k 的小顶堆，堆中存储当前最大的 k 个元素
    // 1. 遍历数组，将元素加入堆
    // 2. 当堆大小超过 k 时，弹出堆顶（最小的元素），保证堆中始终是当前最大的 k 个元素
    // 3. 遍历结束后，堆顶就是第 k 大的元素
    static int FindKthLargestHeap(int[] nums, int k)
    {
        // C# 的 PriorityQueue 是最小堆，默认按优先级升序排列
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();

        foreach (int num in nums)
        {
            // 将当前元素加入堆，优先级为元素值本身
            minHeap.Enqueue(num, num);

            // 如果堆大小超过 k，弹出堆顶（最小的元素）
            if (minHeap.Count > k)
            {
                minHeap.Dequeue();
            }
        }

        // 堆顶就是第 k 大的元素
        return minHeap.Peek();
    }

    #endregion
}

215.4 运行结果

示例1 快速选择 方法 输入：[3,2,1,5,6,4], k=2 输出：5
示例1 小顶堆 方法 输入：[3,2,1,5,6,4], k=2 输出：5
示例2 快速选择 方法 输入：[3,2,3,1,2,4,5,5,6], k=4 输出：4
示例2 小顶堆 方法 输入：[3,2,3,1,2,4,5,5,6], k=4 输出：4
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏