数组中的第K个最大元素

Posted on Edited on In

题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，这里的第 k 个最大元素是指按数组元素从大到小排序后的第 k 个元素，而不是第 k 个不同的元素。

输入格式
输入共 3 行：

  • 第一行包含一个整数 n，表示数组的长度。
  • 第二行包含 n 个整数，表示数组的元素。
  • 第三行包含一个整数 k，表示要找的第 k 个最大元素。

输出格式
输出共 1 行，包含一个整数，表示数组中的第 k 个最大元素。

数据范围
1 ≤ k ≤ n ≤ 10^4
-10^4 ≤ nums[i] ≤ 10^4

输入样例1：

1
2
3
6
3 2 1 5 6 4
2

输出样例1：

1
5

输入样例2：

1
2
3
3
3 2 3 1 2 4 5 5 6
4

输出样例2：

1
4

注意事项

  • 可以使用排序算法将数组排序，然后取第 k 个最大元素，时间复杂度为O(n log n)。
  • 使用小顶堆可以将时间复杂度优化到O(n log k)，空间复杂度为O(k)。
  • 在C++中，可以使用优先队列（默认是大顶堆）来实现小顶堆。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// 方法一：排序法
int findKthLargestSort(vector<int>& nums, int k)
{
    sort(nums.begin(), nums.end(), greater<int>()); // 降序排序
    return nums[k - 1]; // 返回第k个最大元素
}

// 方法二：小顶堆法
int findKthLargestHeap(vector<int>& nums, int k)
{
    priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆
    
    // 先将前k个元素加入堆
    for (int i = 0; i < k; i++)
    {
        minHeap.push(nums[i]);
    }
    
    // 遍历剩余元素
    for (int i = k; i < nums.size(); i++)
    {
        // 如果当前元素比堆顶元素大，则替换堆顶元素
        if (nums[i] > minHeap.top())
        {
            minHeap.pop();
            minHeap.push(nums[i]);
        }
    }
    
    // 堆顶元素即为第k个最大元素
    return minHeap.top();
}

int main()
{
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    
    int k;
    cin >> k;
    
    // 使用小顶堆法求解
    int result = findKthLargestHeap(nums, k);
    
    // 如果要使用排序法，可以取消下面这行的注释，并注释掉上面这行
    // int result = findKthLargestSort(nums, k);
    
    cout << result << endl;
    
    return 0;
}

时间复杂度

  • 排序法时间复杂度：O(n log n)，其中 n 是数组的长度。
  • 小顶堆法时间复杂度：O(n log k)，其中 n 是数组的长度，k 是要找的第 k 个最大元素。
  • 空间复杂度：O(1)（排序法，原地排序）或 O(k)（小顶堆法，用于存储堆）。

代码解释

  • 查找数组中的第 k 个最大元素有两种常见的方法：排序法和小顶堆法。
  • 排序法的思想很简单：将数组降序排序后，返回第 k-1 个元素（数组索引从0开始）。这种方法的实现简单，但时间复杂度较高。
  • 小顶堆法的思想是：维护一个大小为 k 的小顶堆，堆中存储当前找到的前 k 个最大元素。遍历数组时，如果当前元素比堆顶元素大，则替换堆顶元素，并调整堆。遍历结束后，堆顶元素即为第 k 个最大元素。这种方法的时间复杂度较低，特别是当 k 远小于 n 时。
  • 在C++中，可以使用优先队列（priority_queue）来实现小顶堆。默认情况下，priority_queue 是大顶堆，但可以通过传入 greater 作为比较函数来创建小顶堆。