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

海边的西西弗斯

于 2020-06-27 16:38:32 发布

阅读量166

点赞数

分类专栏：刷题

本文链接：https://blog.csdn.net/Protocols7/article/details/106983921

版权

刷题专栏收录该内容

5 篇文章

订阅专栏

本文探讨了寻找数组中第K大的元素的两种方法：排序和小顶堆。排序法直接对数组进行排序，时间复杂度为O(nlog2n)；小顶堆法使用优先队列维护前K大元素，效率更高。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

暴力法

排序，然后找出第n-k个最大的数。

int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }

时间复杂度 $O（nlog_2n）$

小顶堆

int findKthLargest(vector<int>& nums, int k)
{
    priority_queue<int, vector<int>, greater<int>> pq;
    for (auto& n : nums)
    {
        if (pq.size() >= k && pq.top() >= n) continue;
        pq.push(n);
        if (pq.size() > k)
        {
            pq.pop();
        }
    }
    return pq.top();
}