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
//升序队列(小根堆)
priority_queue <int,vector
另外,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)用法详解