当前位置：首页 > article >正文

数组中的第 K 个最大元素（C++实现）

article 2024/9/22 15:27:30

数组中的第 K 个最大元素

题目
思路
代码

题目

数组中的第 K 个最大元素

在这里插入图片描述

思路

通过使用优先队列（最大堆）来找到数组中第k大的元素。通过弹出最大堆中的前k-1个元素，留下堆中的顶部元素作为结果返回。

代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end());
        int i=0;
        while(i<k-1)
        {
            pq.pop();
            i++;
        }
        return pq.top();
    }
};

代码讲解：

priority_queue<int> pq(nums.begin(), nums.end());

在函数内部，创建了一个名为pq的优先队列（优先级队列），它是一个最大堆。通过将nums数组的元素从begin()到end()范围内添加到优先队列中，初始化了一个包含数组所有元素的最大堆。

int i = 0;
        while (i < k - 1) {
            pq.pop();
            i++;
        }

接下来，使用一个循环，执行k-1次pq.pop()操作，将最大堆中的前k-1个元素弹出。由于最大堆的性质，每次弹出的都是当前堆中的最大元素。

return pq.top();
    }
};

最后，返回最大堆中的顶部元素，即第k大的元素。由于最大堆的性质，堆顶元素即为堆中的最大元素。

下面是添加了注释的代码：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 创建一个最大堆，用于存储数组元素
        priority_queue<int> pq(nums.begin(), nums.end());

        int i = 0;
        // 弹出最大堆中的前 k-1 个元素
        while (i < k - 1) {
            pq.pop();
            i++;
        }

        // 返回最大堆的顶部元素，即第 k 大的元素
        return pq.top();
    }
};