原题链接🔗：数组中的第K个最大元素
难度：中等⭐️⭐️

题目

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

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

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

示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

堆

• 堆（Heap）是一种特殊的树状数据结构，它满足两个主要特性：

  1. 结构性：堆通常是一棵完全二叉树，这意味着除了最后一层外，其他每一层都被完全填满，并且最后一层的节点尽可能地集中在左侧。

  2. 堆属性：堆中的每一个节点都必须满足特定的顺序要求，这个要求可以是最大堆属性或最小堆属性。

     • 最大堆：任何一个父节点的值都大于或等于它的子节点的值。这意味着堆的根节点是所有节点中的最大值。
     • 最小堆：任何一个父节点的值都小于或等于它的子节点的值。这意味着堆的根节点是所有节点中的最小值。

• 堆在计算机科学中广泛应用于各种算法和数据结构，特别是在需要快速访问最大元素或最小元素的场景中。例如，堆排序算法、优先队列的实现等。

• 在编程语言中，堆通常通过优先队列（Priority Queue）这种抽象数据类型来实现。优先队列允许快速地插入新元素和删除（或检索）最大（或最小）元素。

• 堆的常见操作包括：

  • 插入（Push）：向堆中添加一个新元素。
  • 删除最大/最小元素（Pop）：移除并返回堆中的最大（或最小）元素。
  • 查找最大/最小元素（Peek/Top）：返回堆中的最大（或最小）元素，但不从堆中移除它。

• 堆的实现可以通过数组来完成，其中每个元素的索引和其父节点或子节点的索引之间有一定的数学关系。例如，在数组表示的堆中，一个元素的父节点可以通过(i-1)/2计算得到，其中i是该元素的索引；其子节点可以通过2*i + 1（左子节点）和2*i + 2（右子节点）计算得到。

题解

1. 解题思路：

在LeetCode上解决“数组中的第K个最大元素”问题，通常有几种不同的方法。这里我会介绍两种常见的解题思路：

• 方法一：排序

  1. 排序：首先，对数组进行排序。
  2. 选择：然后，从排序后的数组中选择第K个元素。

  这种方法简单直观，但时间复杂度较高，尤其是在数组很大的情况下。排序通常需要O(n log n)的时间，其中n是数组的长度。

• 方法二：使用堆（优先队列）

  1. 构建最小堆：使用一个容量为K的最小堆来存储数组中的前K个最大元素。
  2. 遍历数组：遍历数组中的每个元素。
     • 如果当前元素大于堆顶元素，并且堆还没有满（堆的大小小于K），则将堆顶元素移除，并将当前元素加入堆中。
     • 如果当前元素大于堆顶元素，并且堆已经满了，那么只需要将堆顶元素移除，并将当前元素加入堆中，这样堆始终保持大小为K。
  3. 堆顶元素：遍历结束后，堆顶元素就是第K个最大元素。

  这种方法的时间复杂度是O(n log K)，因为每个元素最多被比较和交换K次。当K远小于n时，这种方法比排序更高效。

• 方法三：快速选择算法（Quick Select）

  1. 选择主元：类似于快速排序，选择一个主元，将数组分为两部分，一部分包含所有比主元大的元素，另一部分包含所有比主元小的元素。
  2. 定位主元：根据主元的位置，确定第K个最大元素是在左侧还是在右侧。
  3. 递归：根据K的位置，递归地在左侧或右侧执行快速选择。

  快速选择算法的平均时间复杂度是O(n)，但最坏情况下会退化到O(n^2)。

2. c++ demo：

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

// 使用最大堆来找到第K个最大的元素
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> maxHeap;

    for (int num : nums) {
        if (maxHeap.size() < k) {
            maxHeap.push(num);
        }
        else if (num > maxHeap.top()) {
            maxHeap.pop();
            maxHeap.push(num);
        }
    }

    return maxHeap.top();
}

int main() {
    // 测试用例
    vector<int> nums = { 3,2,1,5,6,4 };
    int k = 2;

    // 调用函数并输出结果
    int result = findKthLargest(nums, k);
    cout << "The " << k << "th largest element is " << result << endl;

    return 0;
}

• 输出结果：

The 2th largest element is 5

3. 代码仓库地址：findKthLargest