国家奖学金，最有用的一次。。。

专栏：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算法文档 。