剑指 Offer II 059. 数据流的第 K 大数值

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20059.%20%E6%95%B0%E6%8D%AE%E6%B5%81%E7%9A%84%E7%AC%AC%20K%20%E5%A4%A7%E6%95%B0%E5%80%BC/README.md

剑指 Offer II 059. 数据流的第 K 大数值

题目描述

设计一个找到数据流中第 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 <= 10⁴
0 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
-10⁴ <= val <= 10⁴
最多调用 add 方法 10⁴ 次
题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

注意：本题与主站 703 题相同： https://leetcode.cn/problems/kth-largest-element-in-a-stream/

解法

方法一

Python3

import heapq as hp
class KthLargest:def __init__(self, k: int, nums: List[int]):self.lst=[]self.k=kfor n in nums:self.add(n)        def add(self, val: int) -> int:hp.heappush(self.lst,val)if len(self.lst)>self.k:hp.heappop(self.lst)return self.lst[0]        # Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

Java

class KthLargest {private PriorityQueue<Integer> q;private int size;public KthLargest(int k, int[] nums) {q = new PriorityQueue<>(k);size = k;for (int num : nums) {add(num);}}public int add(int val) {q.offer(val);if (q.size() > size) {q.poll();}return q.peek();}
}/*** Your KthLargest object will be instantiated and called as such:* KthLargest obj = new KthLargest(k, nums);* int param_1 = obj.add(val);*/

C++

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();}
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

Go

type KthLargest struct {h *IntHeapk int
}func Constructor(k int, nums []int) KthLargest {h := &IntHeap{}heap.Init(h)for _, v := range nums {heap.Push(h, v)}for h.Len() > k {heap.Pop(h)}return KthLargest{h: h,k: k,}
}func (this *KthLargest) Add(val int) int {heap.Push(this.h, val)for this.h.Len() > this.k {heap.Pop(this.h)}return this.h.Top()
}func connectSticks(sticks []int) int {h := IntHeap(sticks)heap.Init(&h)res := 0for h.Len() > 1 {val := heap.Pop(&h).(int)val += heap.Pop(&h).(int)res += valheap.Push(&h, val)}return res
}type IntHeap []intfunc (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x
}func (h *IntHeap) Top() int {if (*h).Len() == 0 {return 0}return (*h)[0]
}/*** Your KthLargest object will be instantiated and called as such:* obj := Constructor(k, nums);* param_1 := obj.Add(val);*/

Swift

import Collectionsclass KthLargest {private var h: Heap<Int>private var size: Intinit(_ k: Int, _ nums: [Int]) {h = Heap()size = kfor x in nums {add(x)}}func add(_ val: Int) -> Int {h.insert(val)if h.count > size {h.removeMin()}return h.min!}
}/*** Your KthLargest object will be instantiated and called as such:* let obj = KthLargest(k, nums)* let ret_1: Int = obj.add(val)*/