find-median-from-data-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

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

<ul>
	<li>For example, for <code>arr = [2,3,4]</code>, the median is <code>3</code>.</li>
	<li>For example, for <code>arr = [2,3]</code>, the median is <code>(2 + 3) / 2 = 2.5</code>.</li>
</ul>

Implement the MedianFinder class:

<ul>
	<li><code>MedianFinder()</code> initializes the <code>MedianFinder</code> object.</li>
	<li><code>void addNum(int num)</code> adds the integer <code>num</code> from the data stream to the data structure.</li>
	<li><code>double findMedian()</code> returns the median of all elements so far. Answers within <code>10-5</code> of the actual answer will be accepted.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input
[&quot;MedianFinder&quot;, &quot;addNum&quot;, &quot;addNum&quot;, &quot;findMedian&quot;, &quot;addNum&quot;, &quot;findMedian&quot;]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>-105 &lt;= num &lt;= 105</code></li>
	<li>There will be at least one element in the data structure before calling <code>findMedian</code>.</li>
	<li>At most <code>5 * 104</code> calls will be made to <code>addNum</code> and <code>findMedian</code>.</li>
</ul>

&nbsp;
Follow up:

<ul>
	<li>If all integer numbers from the stream are in the range <code>[0, 100]</code>, how would you optimize your solution?</li>
	<li>If <code>99%</code> of all integer numbers from the stream are in the range <code>[0, 100]</code>, how would you optimize your solution?</li>
</ul>

Find Median from Data Stream

Sliding Window Median

sliding-window-median

滑动窗口中位数

Finding MK Average

finding-mk-average

求出 MK 平均值

Sequentially Ordinal Rank Tracker

sequentially-ordinal-rank-tracker

序列顺序查询

Minimum Operations to Make Median of Array Equal to K

minimum-operations-to-make-median-of-array-equal-to-k

使数组中位数等于 K 的最少操作数

Minimum Operations to Make Subarray Elements Equal

minimum-operations-to-make-subarray-elements-equal

将子数组元素变为相等所需的最小操作数

Minimum Operations to Make Elements Within K Subarrays Equal

minimum-operations-to-make-elements-within-k-subarrays-equal

使 K 个子数组内元素相等的最少操作数

Design

Two Pointers

Data Stream

Sorting

Heap (Priority Queue)

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

<ul>
	<li>例如 <code>arr = [2,3,4]</code>&nbsp;的中位数是 <code>3</code>&nbsp;。</li>
	<li>例如&nbsp;<code>arr = [2,3]</code> 的中位数是 <code>(2 + 3) / 2 = 2.5</code> 。</li>
</ul>

实现 MedianFinder 类:

<ul>
	<li>
	<code>MedianFinder() </code>初始化 <code>MedianFinder</code>&nbsp;对象。
	</li>
	<li>
	<code>void addNum(int num)</code> 将数据流中的整数 <code>num</code> 添加到数据结构中。
	</li>
	<li>
	<code>double findMedian()</code> 返回到目前为止所有元素的中位数。与实际答案相差&nbsp;<code>10-5</code>&nbsp;以内的答案将被接受。
	</li>
</ul>

示例 1：

<pre>
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0</pre>

提示:

<ul>
	<li><code>-105&nbsp;&lt;= num &lt;= 105</code></li>
	<li>在调用 <code>findMedian</code>&nbsp;之前，数据结构中至少有一个元素</li>
	<li>最多&nbsp;<code>5 * 104</code>&nbsp;次调用&nbsp;<code>addNum</code>&nbsp;和&nbsp;<code>findMedian</code></li>
</ul>