sliding-window-median

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. So the median is the mean of the two middle values.

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

You are given an integer array <code>nums</code> and an integer <code>k</code>. There is a sliding window of size <code>k</code> which is moving from the very left of the array to the very right. You can only see the <code>k</code> numbers in the window. Each time the sliding window moves right by one position.

Return the median array for each window in the original array. Answers within <code>10-5</code> of the actual value will be accepted.

&nbsp;
Example 1:

<pre>
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
 1 [3 -1 -3] 5 3 6 7 -1
 1 3 [-1 -3 5] 3 6 7 -1
 1 3 -1 [-3 5 3] 6 7 3
 1 3 -1 -3 [5 3 6] 7 5
 1 3 -1 -3 5 [3 6 7] 6
</pre>

Example 2:

<pre>
Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 105</code></li>
	<li><code>-231 &lt;= nums[i] &lt;= 231 - 1</code></li>
</ul>

medianSlidingWindow

Sliding Window Median

Find Median from Data Stream

find-median-from-data-stream

数据流的中位数

Minimum Operations to Make Median of Array Equal to K

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

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

Array

Hash Table

Sliding Window

Heap (Priority Queue)

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

<ul>
	<li><code>[2,3,4]</code>，中位数是 <code>3</code></li>
	<li><code>[2,3]</code>，中位数是 <code>(2 + 3) / 2 = 2.5</code></li>
</ul>

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

 

示例：

给出 nums = <code>[1,3,-1,-3,5,3,6,7]</code>，以及 k = 3。

<pre>
窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
 1 [3 -1 -3] 5 3 6 7 -1
 1 3 [-1 -3 5] 3 6 7 -1
 1 3 -1 [-3 5 3] 6 7 3
 1 3 -1 -3 [5 3 6] 7 5
 1 3 -1 -3 5 [3 6 7] 6
</pre>

 因此，返回该滑动窗口的中位数数组 <code>[1,-1,-1,3,5,6]</code>。

 

提示：

<ul>
	<li>你可以假设 <code>k</code> 始终有效，即：<code>k</code> 始终小于等于输入的非空数组的元素个数。</li>
	<li>与真实值误差在 <code>10 ^ -5</code> 以内的答案将被视作正确答案。</li>
</ul>