kth-largest-element-in-a-stream

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are part of a university admissions office and need to keep track of the <code>kth</code> 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&nbsp;<code>k</code>, maintains a stream of test scores and continuously returns the&nbsp;<code>k</code>th highest test score&nbsp;after&nbsp;a new score has been submitted. More specifically, we are looking for the <code>k</code>th highest score in the sorted list of all scores.

Implement the&nbsp;<code>KthLargest</code> class:

<ul>
	<li><code>KthLargest(int k, int[] nums)</code> Initializes the object with the integer <code>k</code> and the stream of test scores&nbsp;<code>nums</code>.</li>
	<li><code>int add(int val)</code> Adds a new test score&nbsp;<code>val</code> to the stream and returns the element representing the <code>kth</code> largest element in the pool of test scores so far.</li>
</ul>

&nbsp;
Example 1:

<div class="example-block">
Input: 
[&quot;KthLargest&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;] 
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output: [null, 4, 5, 5, 8, 8]

Explanation:

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
</div>

Example 2:

<div class="example-block">
Input: 
[&quot;KthLargest&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;] 
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

Output: [null, 7, 7, 7, 8]

Explanation:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]); 
kthLargest.add(2); // return 7 
kthLargest.add(10); // return 7 
kthLargest.add(9); // return 7 
kthLargest.add(9); // return 8</div>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= nums.length &lt;= 104</code></li>
	<li><code>1 &lt;= k &lt;= nums.length + 1</code></li>
	<li><code>-104 &lt;= nums[i] &lt;= 104</code></li>
	<li><code>-104 &lt;= val &lt;= 104</code></li>
	<li>At most <code>104</code> calls will be made to <code>add</code>.</li>
</ul>

Kth Largest Element in a Stream

Kth Largest Element in an Array

kth-largest-element-in-an-array

数组中的第K个最大元素

Finding MK Average

finding-mk-average

求出 MK 平均值

Sequentially Ordinal Rank Tracker

sequentially-ordinal-rank-tracker

序列顺序查询

Tree

Design

Binary Search Tree

Binary Tree

Data Stream

Heap (Priority Queue)

设计一个找到数据流中第 <code>k</code> 大元素的类（class）。注意是排序后的第 <code>k</code> 大元素，不是第 <code>k</code> 个不同的元素。

请实现 <code>KthLargest</code>&nbsp;类：

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

&nbsp;

示例 1：

<div class="example-block">
输入： 
["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); // 返回 4 
kthLargest.add(5); // 返回 5 
kthLargest.add(10); // 返回 5 
kthLargest.add(9); // 返回 8 
kthLargest.add(4); // 返回 8

&nbsp;
</div>

示例&nbsp;2：

<div class="example-block">
输入： 
["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</div>

&nbsp;
提示：

<ul>
	<li><code>0 &lt;= nums.length &lt;= 104</code></li>
	<li><code>1 &lt;= k &lt;= nums.length + 1</code></li>
	<li><code>-104 &lt;= nums[i] &lt;= 104</code></li>
	<li><code>-104 &lt;= val &lt;= 104</code></li>
	<li>最多调用 <code>add</code> 方法 <code>104</code> 次</li>
</ul>