[leetcode] 0703.数据流中的第k大元素-编程思维

703. 数据流中的第 K 大元素

点击上方标题跳转至leetcode

题目描述

设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。

请实现 KthLargest 类:

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val)val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。

 

示例:

输入:
["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);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

提示:
  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104
  • 题目数据保证,在查找第 k 大元素时,数组中至少有 k 个元素

解法

使用大小为 K 的小根堆,在初始化的时候,保证堆中的元素个数不超过 K 。
在每次 add() 的时候,将新元素 push() 到堆中,如果此时堆中的元素超过了 K,那么需要把堆中的最小元素(堆顶)pop() 出来。
此时堆中的最小元素(堆顶)就是整个数据流中的第 K 大元素。

Python3

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.q = []
        self.size = k
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.q, val)
        # print(self.q)
        if len(self.q) > self.size:
            heapq.heappop(self.q)
            # print(self.q)
        return self.q[0]
        
nums = [4,5,8,2]
k = 3
kthLargest = KthLargest(k, nums)
param_1 = kthLargest.add(3)
param_2 = kthLargest.add(5)
param_3 = kthLargest.add(10)
param_4 = kthLargest.add(9)
param_5 = kthLargest.add(4)

print(param_1)
print(param_2)
print(param_3)
print(param_4)
print(param_5)

C++

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> q;
    int size;
    KthLargest(int k, vector<int>& nums) {
        size = k;
        for (int num : nums) add(num);
    }
    int add(int val) {
        q.push(val);
        if (q.size() > size) q.pop();
        return q.top();
    }
};

int main(){

    vector<int> nums = {4,5,8,2};
    int k = 3;
    KthLargest* obj = new KthLargest(k, nums);
    int param_1 = obj->add(3);
    int param_2 = obj->add(5);
    int param_3 = obj->add(10);
    int param_4 = obj->add(9);
    int param_5 = obj->add(4);
    // int res1 = KthLargest(k,nums).add(3);
    cout << param_1 << "\t" 
         << param_2 << "\t"  
         << param_3 << "\t"  
         << param_4 << "\t"  
         << param_5 << "\t" << endl;
    delete obj;
    return 0;
}
//g++ 703.cpp -std=c++11

时间复杂度:

初始化时间复杂度为:O(nlogk) ,其中 n 为初始化时 nums 的长度;
单次插入时间复杂度为:O(logk)
空间复杂度:O(k)需要使用优先队列存储前 k 大的元素;

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/yege/p/17374400.html

[leetcode] 0705. 设计哈希集合-编程思维

705. 设计哈希集合 English Version 题目描述 不使用任何内建的哈希表库设计一个哈希集合(HashSet)。 实现 MyHashSet 类: void add(key) 向哈希集合中插入值 key 。 bool contains(key) 返回哈希集合中是否存在这个值 key 。 void

【leetcode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)-编程思维

最长递增子序列 力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums

[leetcode] 0697.数组的度-编程思维

697. 数组的度 点击上方标题跳转至leetcode 题目描述 给定一个非空且只包含非负数的整数数组 nums,数组的 度 的定义是指数组里任一元素出现频数的最大值。 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。   示例 1: 输入:nums = [1,2,2,3,1

[leetcode] 0696. 计数二进制子串-编程思维

696. 计数二进制子串 点击上方链接跳转至leetcode 题目描述 给定一个字符串 s,统计并返回具有相同数量 0 和 1 的非空(连续)子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是成组连续的。 重复出现(不同位置)的子串也要统计它们出现的次数。   示例 1: 输入:s = "00110011

[leetcode] 0693. 交替位二进制数-编程思维

693. 交替位二进制数 点击上方标题跳转至leetcode 题目描述 给定一个正整数,检查它的二进制表示是否总是 0、1 交替出现:换句话说,就是二进制表示中相邻两位的数字永不相同。   示例 1: 输入:n = 5 输出:true 解释:5 的二进制表示是:101 示例 2: 输入:n = 7 输出:false