专栏首页计算机视觉与深度学习基础Leetcode 215. Kth Largest Element in an Array

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, Given [3,2,1,5,6,4] and k = 2, return 5.

找出无序数组中第k大的数,维护一个最小堆,使得堆的大小始终等于k,最后堆顶元素为结果。

优先队列的stl忘记了,greater是最小堆,less是最大堆,记住了!

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i = 0; i < nums.size(); i++)
        {
            q.push(nums[i]);
            if(q.size() > k) q.pop();
        }
        return q.top();
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 169 Majority Element

    Given an array of size n, find the majority element. The majority element is th...

    triplebee
  • Leetcode 75 Sort Colors

    Given an array with n objects colored red, white or blue, sort them so that obj...

    triplebee
  • Leercode 35 Search Insert Position

    Given a sorted array and a target value, return the index if the target is foun...

    triplebee
  • C++快速排序原理深究优化

    前面写过一篇关于归并和快排的文章《归并快排算法比较及求第K大元素》,但文中实现的快排算法,在某些极端情况下时间复杂度会退化到 O(n2),效率将是无法接受的。本...

    evenleo
  • 用 WPF 写的颜色拾取器

    之前都是用别人的颜色拾取器,今天自己用WPF写了一个颜色拾取器小程序 拾取鼠标所在位置的颜色,按键盘上的空格键停止取色 程序下载:MyWPFScreenColo...

    lpxxn
  • hdu1014

    @坤的
  • 算法复杂度分析

    为什么要进行算法分析? 预测算法所需的资源 计算时间(CPU 消耗) 内存空间(RAM 消耗) 通信时间(带宽消耗) 预测算法的运行时间 在给定输入规模时,所执...

    前朝楚水
  • Leetcode 169 Majority Element

    Given an array of size n, find the majority element. The majority element is th...

    triplebee
  • CVPR论文《100+ Times Faster Weighted Median Filter (WMF)》的实现和解析

    【GiantPandaCV导语】由于太硬核,小编已经写不出来导语了。 请直接阅读正文。本文首发于博客园https://www.cnblogs.com/Image...

    BBuf
  • Array - 239. Sliding Window Maximum

    Given an array nums, there is a sliding window of size k which is moving from th...

    用户5705150

扫码关注云+社区

领取腾讯云代金券