专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友在进入录用阶段之后，因为曾经获得国家奖学金，hr决定在现有的薪资结构上在额外累加500元，这说明奖学金在面试的时候还是有用的。当然大学里的奖学金不一定都是按照考试分数来定的，还有一部分是根据自己平时的表现累加的积分。
记得当年在找工作的时候有的hr直接就说了英语过六级，工资要比没过六级的高一些。这说明奖学金，英语六级(非英语专业的学生)，甚至还有一些计算机证书(三级，四级)在找工作的时候还是有一定的帮助。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第703题：数据流中的第 K 大元素。
问题描述
来源：LeetCode第703题
难度：简单
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
1，KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
2，int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
示例1：
输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出：[null, 4, 5, 5, 8, 8] 解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // 返回 4 kthLargest.add(5); // 返回 5 kthLargest.add(10); // 返回 5 kthLargest.add(9); // 返回 8 kthLargest.add(4); // 返回 8
示例2：
输入： ["KthLargest", "add", "add", "add", "add"] [[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]] 输出：[null, 7, 7, 7, 8] 解释： KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]); kthLargest.add(2); // 返回 7 kthLargest.add(10); // 返回 7 kthLargest.add(9); // 返回 7 kthLargest.add(9); // 返回 8
0 <= nums.length <= 10^4
1 <= k <= nums.length + 1
-10^4 <= nums[i] <= 10^4
-10^4 <= val <= 10^4
最多调用 add 方法 10^4 次
问题分析
这题是让找出数据流排序之后第 k 大的元素，如果每次添加的时候都要排序，这样肯定是不行的， 我们可以使用 最小堆 来解这题。
堆中的元素个数不能超过 k ，当超过的时候就把多余的移除，因为是最小堆，所以移除的肯定是堆中最小的，这样就可以保证 前 k 大的元素都在堆中，其中堆顶元素就是第 k 大的值 。
JAVA：
class KthLargest {
PriorityQueue
pq; // 最小堆 final int k; public KthLargest(int k, int[] nums) { this.k = k; pq = new PriorityQueue<>(k); for ( int num : nums) add(num); } public int add(int val) { pq.offer(val); if (pq.size() > k) // 如果大于k个，把多余的移除。 pq.poll(); return pq.peek(); } }C++：
class KthLargest {
private:
priority_queue
, std::greater<>> pq;// 最小堆 const int k; public: KthLargest(int k, vector
&nums) : k(k) { for (int num: nums) add(num); } int add(int val) { pq.push(val); if (pq.size() > k) pq.pop(); return pq.top(); } };
Python：
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.pq = []
for num in nums:
self.add(num)
def add(self, val: int) -> int:
heapq.heappush(self.pq, val)
if len(self.pq) > self.k:
heapq.heappop(self.pq)
return self.pq[0]笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴