Leetcode 703. 数据流中的第K大元素

Stella981
• 阅读 654

1.题目要求

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 **KthLargest.add**,返回当前数据流中第K大的元素。

示例:

int k = 3;
  int[] arr = [4,5,8,2];
  KthLargest kthLargest = new KthLargest(3, arr);
  kthLargest.add(3);   // returns 4
  kthLargest.add(5);   // returns 5
  kthLargest.add(10);  // returns 5
  kthLargest.add(9);   // returns 8
  kthLargest.add(4);   // returns 8

说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。

2.解题思路

一般地,堆和堆排序——解决 "贪心算法及其类似问题" 的利器。

# 思路:我们可以用一个小根堆来做,并且限制堆的大小为k,初始化时把nums的每个数都push到堆中,如果堆的大小大于k,就pop一个元素。对于add方法也是同理。

# 这里使用的数据结构是C++中的“优先队列(priority_queue)",包含在头文件中。优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的。

_定义:priority_queue<Type, Container, Functional>
_

Type 就是数据类型,

Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),

Functional 就是比较的方式,当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大根堆 。

//降序队列(大根堆)
priority_queue <int,vector,less >q;

//升序队列(小根堆)
priority_queue <int,vector,greater > q;

另外,greater和less是std实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了)

//示例#include<iostream>
#include <queue>
using namespace std;
int main() { //对于基础类型 默认是大顶堆  priority_queue<int> a; //等同于 priority_queue<int, vector<int>, less<int> > a; // 这里一定要有空格,不然成了右移运算符↓  priority_queue<int, vector<int>, greater<int> > c; //这样就是小顶堆  priority_queue<string> b; for (int i = 0; i < 5; i++) { a.push(i); c.push(i); } while (!a.empty()) { cout << a.top() << ' '; a.pop(); } cout << endl; while (!c.empty()) { cout << c.top() << ' '; c.pop(); } cout << endl; b.push("abc"); b.push("abcd"); b.push("cbd"); while (!b.empty()) { cout << b.top() << ' '; b.pop(); } cout << endl; return 0; }

//输出

4 3 2 1 0
0 1 2 3 4
cbd abcd abc

3.我的代码

Leetcode上提交的执行时间为36ms.

/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/

class KthLargest {
public:
    KthLargest(int k, vector<int> nums) {
        //限制堆的大小为k
        size = k;
        
        for (int i = 0; i < nums.size(); i++){            
            heap.push(nums[i]);

            //堆大小超过k,pop出一个元素            
            if (heap.size() > k) heap.pop();        
        }    
    }    
        //操作原理同上
        int add(int val) {        
            heap.push(val);        
            if (heap.size() > size) heap.pop();        
            return heap.top();    }

private:
    //升序队列(小根堆),STL中存在的一种优先队列,本质用堆实现的
    priority_queue<int, vector<int>, greater<int>> heap;    
    int size;
};
 

4.用时更少的范例

这是leetcode上执行时间最短的提交代码,执行时间为28ms。思路同上,代码几乎相同。虽然运行快了一些,但是个人认为上面解法中的代码写法更加安全规范

因为,一般“数据元素”都是定为private的,这样程序安全性更高。

class KthLargest {
public:

    //定义放在前面了
    priority_queue<int, vector<int>, greater<int>> pq;
    int size;

    KthLargest(int k, vector<int> nums) {
        size=k;
        for(int i=0;i<nums.size();i++) {
            pq.push(nums[i]);
            if(pq.size()>k) pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if(pq.size()>size) pq.pop();
        return pq.top();
    }
};
 

参考博客:

_1:https://blog.csdn.net/qq_26410101/article/details/81977685     Kth Largest Element in a Stream 数据流中的第K大元素
_

2:https://blog.csdn.net/weixin_36888577/article/details/79937886    c++优先队列(priority_queue)用法详解

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
DaLongggggg DaLongggggg
3年前
python-算法训练 区间k大数查询
问题描述给定一个序列,每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n,表示序列长度。第二行包含n个正整数,表示给定的序列。第三个包含一个正整数m,表示询问个数。接下来m行,每行三个数l,r,K,表示询问序列从左往右第l个数到第r个数中,从大往小第K大的数是哪个。序列元素从1开始标号。输出格式总共输出m行,每行一个数
Stella981 Stella981
3年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
Java面试总结(排序算法)
1.冒泡排序算法描述:两两比较,大的放后面2.选择排序算法描述:在m元数组中找到最小值的位置,然后将最小值的位置和第n(n0,1,2,....m1)位的值对调,排序k次则m元数组中前k(k<m)位的值已经排序好,m元数组中前k位的值不需要再进行排序,此时需要排序的元素只有mk个3.插入排序算
Stella981 Stella981
3年前
LeetCode 230. 二叉搜索树中第K小的元素(Kth Smallest Element in a BST)
题目描述给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明:你可以假设k总是有效的,1≤k≤二叉搜索树元素个数。示例1:输入:root3,1,4,null,2,k13/\14
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这