Algorithm
Problem Name: 480. Sliding Window Median
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.
- For examples, if
arr = [2,3,4], the median is3. - For examples, if
arr = [1,2,3,4], the median is(2 + 3) / 2 = 2.5.
You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k 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 10-5 of the actual value will be accepted.
Example 1:
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
Example 2:
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]
Constraints:
1 <= k <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
List list;
double[] ans;
boolean isEven;
public double[] medianSlidingWindow(int[] nums, int k) {
list = new ArrayList < >();
ans = new double[nums.length - k + 1];
isEven = k % 2 == 0;
for (int i=0; i < k; i++) {
list.add((long) nums[i]);
}
Collections.sort(list);
int idx = 0;
ans[idx++] = getMedian();
for (int i=k; i < nums.length; i++) {
removeElement(nums[idx - 1]);
int tempIdx = getBinarySearchIdx(nums[i]);
list.add(tempIdx, (long) nums[i]);
ans[idx++] = getMedian();
}
return ans;
}
private int getBinarySearchIdx(int num) {
if (list.size() == 0 || num < list.get(0)) {
return 0;
}
if (num > list.get(list.size() - 1)) {
return list.size();
}
int start = 0;
int end = list.size();
while (start < end) {
int mid = (start + end) / 2;
if (list.get(mid) < num) {
start = mid + 1;
}
else {
end = mid;
}
}
return end;
}
private void removeElement(int num) {
for (int i=0; i < list.size(); i++) {
if (list.get(i) == num) {
list.remove(i);
break;
}
}
}
private double getMedian() {
if (isEven) {
return (double) (list.get(list.size()/2) + list.get(list.size()/2 - 1)) / 2;
}
else {
return (double) list.get(list.size()/2);
}
}
}
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]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const medianSlidingWindow = function(nums, k) {
const window = nums.slice(0, k).sort((x, y) => x - y)
const resultLen = nums.length - k + 1
nums.push(0)
function insert(arr, val) {
let i = 0
while (i < arr.length && arr[i] < val) {
i++
}
arr.splice(i, 0, val)
}
const medians = []
const rightIdx = (k / 2) >>> 0
const leftIdx = k + ~rightIdx
for (let i = 0; i < resultLen; i++) {
medians.push((window[leftIdx] + window[rightIdx]) / 2)
window.splice(window.indexOf(nums[i]), 1)
insert(window, nums[k + i])
}
return medians
}
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]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def medianSlidingWindow(self, nums, k):
window = sorted(nums[:k])
medians = []
for a, b in zip(nums, nums[k:] + [0]):
medians.append((window[k//2] + window[~(k//2)]) / 2.)
window.remove(a)
bisect.insort(window, b)
return medians
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]
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0480_SlidingWindowMedian
{
public double[] MedianSlidingWindow(int[] nums, int k)
{
// SortedDictionary.Keys.First() is must faster than SortedDictionary.Keys.Last() (terraible implementation of .net)
var left = new SortedDictionary < long, int>(Comparer.Create((x, y) => y.CompareTo(x)));
var leftCount = 0;
var right = new SortedDictionary < long, int>();
var rightCount = 0;
var result = new List < double>(nums.Length - k + 1);
for (int i = 0; i < nums.Length; i++)
{
if (i >= k)
{
if (rightCount > leftCount) result.Add(right.Keys.First());
else result.Add((right.Keys.First() + left.Keys.First()) / 2.0);
if (right.ContainsKey(nums[i - k]))
{
right[nums[i - k]]--;
if (right[nums[i - k]] == 0) right.Remove(nums[i - k]);
rightCount--;
}
else if (left.ContainsKey(nums[i - k]))
{
left[nums[i - k]]--;
if (left[nums[i - k]] == 0) left.Remove(nums[i - k]);
leftCount--;
}
}
if (!right.ContainsKey(nums[i]))
right[nums[i]] = 1;
else
right[nums[i]]++;
rightCount++;
var minRight = right.Keys.First();
right[minRight]--;
if (right[minRight] == 0) right.Remove(minRight);
rightCount--;
if (!left.ContainsKey(minRight))
left[minRight] = 1;
else
left[minRight]++;
leftCount++;
if (rightCount < leftCount)
{
var maxLeft = left.Keys.First();
left[maxLeft]--;
if (left[maxLeft] == 0) left.Remove(maxLeft);
leftCount--;
if (!right.ContainsKey(maxLeft))
right[maxLeft] = 1;
else
right[maxLeft]++;
rightCount++;
}
}
if (rightCount > leftCount) result.Add(right.Keys.First());
else result.Add((right.Keys.First() + left.Keys.First()) / 2.0);
return result.ToArray();
}
}
}
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]