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

数据结构和算法 2024-09-19 发布于上海

展开全文

精品推荐：

《征服数据结构》专栏：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<Integer> 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<int, std::vector<int>, std::greater<>> pq;// 最小堆
    const int k;

public:
    KthLargest(int k, vector<int> &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]