You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.
You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.
Implement the KthLargest class:
KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.
int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.
We maintain a priority queue (min heap) $\textit{minQ}$.
Initially, we add the elements of the array $\textit{nums}$ to $\textit{minQ}$ one by one, ensuring that the size of $\textit{minQ}$ does not exceed $k$. The time complexity is $O(n \times \log k)$.
Each time a new element is added, if the size of $\textit{minQ}$ exceeds $k$, we pop the top element of the heap to ensure that the size of $\textit{minQ}$ is $k$. The time complexity is $O(\log k)$.
In this way, the elements in $\textit{minQ}$ are the largest $k$ elements in the array $\textit{nums}$, and the top element of the heap is the $k^{th}$ largest element.
The space complexity is $O(k)$.
1 2 3 4 5 6 7 8 9101112131415161718
classKthLargest:def__init__(self,k:int,nums:List[int]):self.k=kself.min_q=[]forxinnums:self.add(x)defadd(self,val:int)->int:heappush(self.min_q,val)iflen(self.min_q)>self.k:heappop(self.min_q)returnself.min_q[0]# Your KthLargest object will be instantiated and called as such:# obj = KthLargest(k, nums)# param_1 = obj.add(val)
classKthLargest{privatePriorityQueue<Integer>minQ;privateintk;publicKthLargest(intk,int[]nums){this.k=k;minQ=newPriorityQueue<>(k);for(intx:nums){add(x);}}publicintadd(intval){minQ.offer(val);if(minQ.size()>k){minQ.poll();}returnminQ.peek();}}/** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */
classKthLargest{public:KthLargest(intk,vector<int>&nums){this->k=k;for(intx:nums){add(x);}}intadd(intval){minQ.push(val);if(minQ.size()>k){minQ.pop();}returnminQ.top();}private:intk;priority_queue<int,vector<int>,greater<int>>minQ;};/** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */
typeKthLargeststruct{kintminQhp}funcConstructor(kint,nums[]int)KthLargest{minQ:=hp{}this:=KthLargest{k,minQ}for_,x:=rangenums{this.Add(x)}returnthis}func(this*KthLargest)Add(valint)int{heap.Push(&this.minQ,val)ifthis.minQ.Len()>this.k{heap.Pop(&this.minQ)}returnthis.minQ.IntSlice[0]}typehpstruct{sort.IntSlice}func(h*hp)Less(i,jint)bool{returnh.IntSlice[i]<h.IntSlice[j]}func(h*hp)Pop()interface{}{old:=h.IntSlicen:=len(old)x:=old[n-1]h.IntSlice=old[0:n-1]returnx}func(h*hp)Push(xinterface{}){h.IntSlice=append(h.IntSlice,x.(int))}/** * Your KthLargest object will be instantiated and called as such: * obj := Constructor(k, nums); * param_1 := obj.Add(val); */
1 2 3 4 5 6 7 8 910111213141516171819202122232425
classKthLargest{#k:number=0;#minQ=newMinPriorityQueue();constructor(k:number,nums:number[]){this.#k=k;for(constxofnums){this.add(x);}}add(val:number):number{this.#minQ.enqueue(val);if(this.#minQ.size()>this.#k){this.#minQ.dequeue();}returnthis.#minQ.front().element;}}/** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */
/** * @param {number} k * @param {number[]} nums */varKthLargest=function(k,nums){this.k=k;this.minQ=newMinPriorityQueue();for(constxofnums){this.add(x);}};/** * @param {number} val * @return {number} */KthLargest.prototype.add=function(val){this.minQ.enqueue(val);if(this.minQ.size()>this.k){this.minQ.dequeue();}returnthis.minQ.front().element;};/** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */