• 耳光 调教 国度奖学金,最灵验的一次。。。|算法|pq|数据流|add|spiderlinebreak

    发布日期:2024-10-07 21:37    点击次数:160

    耳光 调教 国度奖学金,最灵验的一次。。。|算法|pq|数据流|add|spiderlinebreak

    少妇图片

    专栏: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,bt核工厂发布器 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算法文档 。