Welcome to Subscribe On Youtube
-
import java.util.PriorityQueue; /** Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Your Kth Largest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream. Example: int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8 Note: You may assume that nums' length ≥ k-1 and k ≥ 1. @tag-array */ public class Kth_Largest_Element_in_a_Stream { class KthLargest { final PriorityQueue<Integer> q; final int k; public KthLargest(int k, int[] nums) { this.k = k; q = new PriorityQueue<>(k); for (int n : nums) { add(n); } } public int add(int n) { if (q.size() < k) { q.offer(n); } else if (q.peek() < n) { q.poll(); q.offer(n); } 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); */ } ############ 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); */ -
// OJ: https://leetcode.com/problems/kth-largest-element-in-a-stream/ // Time: // KthLargest: O(NlogK) // add: O(logK) // Space: O(N) class KthLargest { private: priority_queue<int, vector<int>, greater<>> pq; int k; public: KthLargest(int k, vector<int> A): k(k) { for (int n : A) { pq.push(n); if (pq.size() > k) pq.pop(); } } int add(int val) { pq.push(val); if (pq.size() > k) pq.pop(); return pq.top(); } }; -
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: heappush(self.q, val) if len(self.q) > self.size: heappop(self.q) return self.q[0] # Your KthLargest object will be instantiated and called as such: # obj = KthLargest(k, nums) # param_1 = obj.add(val) ############ class KthLargest(object): def __init__(self, k, nums): """ :type k: int :type nums: List[int] """ self.pool = nums self.size = len(self.pool) self.k = k heapq.heapify(self.pool) while self.size > k: heapq.heappop(self.pool) self.size -= 1 def add(self, val): """ :type val: int :rtype: int """ if self.size < self.k: heapq.heappush(self.pool, val) self.size += 1 elif val > self.pool[0]: heapq.heapreplace(self.pool, val) return self.pool[0] # Your KthLargest object will be instantiated and called as such: # obj = KthLargest(k, nums) # param_1 = obj.add(val) -
type KthLargest struct { h *IntHeap k 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 := 0 for h.Len() > 1 { val := heap.Pop(&h).(int) val += heap.Pop(&h).(int) res += val heap.Push(&h, val) } return res } type IntHeap []int func (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 interface{}) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { old := *h n := 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); */ -
/** * @param {number} k * @param {number[]} nums */ var KthLargest = function (k, nums) { this.k = k; this.heap = new MinHeap(); for (let num of nums) { this.add(num); } }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function (val) { this.heap.offer(val); if (this.heap.size() > this.k) { this.heap.poll(); } return this.heap.peek(); }; class MinHeap { constructor(data = []) { this.data = data; this.comparator = (a, b) => a - b; this.heapify(); } heapify() { if (this.size() < 2) return; for (let i = 1; i < this.size(); i++) { this.bubbleUp(i); } } peek() { if (this.size() === 0) return null; return this.data[0]; } offer(value) { this.data.push(value); this.bubbleUp(this.size() - 1); } poll() { if (this.size() === 0) { return null; } const result = this.data[0]; const last = this.data.pop(); if (this.size() !== 0) { this.data[0] = last; this.bubbleDown(0); } return result; } bubbleUp(index) { while (index > 0) { const parentIndex = (index - 1) >> 1; if (this.comparator(this.data[index], this.data[parentIndex]) < 0) { this.swap(index, parentIndex); index = parentIndex; } else { break; } } } bubbleDown(index) { const lastIndex = this.size() - 1; while (true) { const leftIndex = index * 2 + 1; const rightIndex = index * 2 + 2; let findIndex = index; if ( leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 ) { findIndex = leftIndex; } if ( rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 ) { findIndex = rightIndex; } if (index !== findIndex) { this.swap(index, findIndex); index = findIndex; } else { break; } } } swap(index1, index2) { [this.data[index1], this.data[index2]] = [ this.data[index2], this.data[index1], ]; } size() { return this.data.length; } } /** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */