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 条评论
登录 后参与评论

相关文章

来自专栏Android机动车

数据结构学习笔记——队列

线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。

5810
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二叉树中和为某一值的路径(九度OJ1368)

题目描述: 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 输入:...

21270
来自专栏LanceToBigData

Java集合源码分析(三)Vevtor和Stack

前言   前面写了一篇关于的是LinkedList的除了它的数据结构稍微有一点复杂之外,其他的都很好理解的。这一篇讲的可能大家在开发中很少去用到。但是有的时候也...

25960
来自专栏Java编程

Java HashMap那点事

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

43500
来自专栏阿杜的世界

Java并发-CopyOnWriteArrayList前言CopyOnWriteArrayList API例子1:插入(删除)数据的同时进行遍历例子2:不支持一边遍历一边删除结论参考资料

今天我们一起学习下java.util.concurrent并发包里的CopyOnWriteArrayList工具类。当有多个线程可能同时遍历、修改某个公共数组时...

15730
来自专栏落花落雨不落叶

线性表学习

350100
来自专栏小灰灰

JDK容器学习之List: CopyOnWriteArrayList,ArrayList,LinkedList对比

列表 List, ArrayList, LinkedList, CopyOnWriteArrayList, Vector 简述 1. 列表划分为线程安全和线程...

219100
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

11730
来自专栏计算机视觉与深度学习基础

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the lar...

263100
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十九】Iterator&fail-fast机制

【Java提高十九】Iterator&fail-fast机制 Iterator详解 迭代对于我们搞Java的来说绝对不陌生。我们常常使用JDK提供的迭代接口进行...

411110

扫码关注云+社区

领取腾讯云代金券