# leetcode480. Sliding Window Median

## 题目要求

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 value.

Examples: [2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, 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. Your job is to output the median array for each window in the original array.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

```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```

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note: You may assume k is always valid, ie: k is always smaller than input array's size for non-empty array.

## 思路和代码

```    public double[] medianSlidingWindow(int[] nums, int k) {
Queue<Integer> small = new PriorityQueue<>(Comparator.reverseOrder());
Queue<Integer> large = new PriorityQueue<>();

double[] result = new double[nums.length - k + 1];
boolean isEven = k % 2 == 0;
for (int i = 0; i < nums.length; i++) {
large.offer(nums[i]);
small.offer(large.poll());
if (large.size() < small.size()) {
large.offer(small.poll());
}
if (small.size() + large.size() < k) {
continue;
}

double median = isEven ? ((double) large.peek() + (double) small.peek()) / 2.0 : (double) large.peek();
result[i - k + 1] = median;
if (large.peek() <= nums[i - k + 1]) {
large.remove(nums[i - k + 1]);
} else {
small.remove(nums[i - k + 1]);
}
}
return result;
}```

```    Node root;

public double[] medianSlidingWindow(int[] nums, int k) {
if (nums.length == 0)
return new double[0];
if (k == 1) {
double[] medians = new double[nums.length];
for (int i = 0; i < nums.length; ++i)
medians[i] = (double) nums[i];
return medians;
}
double[] medians = new double[nums.length - k + 1];

for (int i = 0; i < k; ++i) {
insert(nums[i]);
}

if (k % 2 == 1) {
medians[0] = (double) search(root, k / 2 + 1, 0);
} else {
medians[0] = ((double) search(root, k / 2, 0) + (double) search(root, k / 2 + 1, 0)) / 2;
}

for (int i = k; i < nums.length; ++i) {
delete(root, nums[i - k]);
insert(nums[i]);
if (k % 2 == 1) {
medians[i - k + 1] = (double) search(root, k / 2 + 1, 0);
} else {
medians[i - k + 1] = ((double) search(root, k / 2, 0) + (double) search(root, k / 2 + 1, 0)) / 2;
}
}

return medians;
}

private static class Node {
int key;
int cnt;
int leftSize;
Node left;
Node right;

public Node(int k) {
key = k;
cnt = 1;
leftSize = 0;
left = null;
right = null;
}
}

private void insert(int k) {
Node x = root;
if (x == null) {
root = new Node(k);
return;
}
while (true) {
if (x.key == k) {
x.cnt++;
return;
} else if (x.key > k) {
x.leftSize++;
if (x.left == null) {
x.left = new Node(k);
return;
}
x = x.left;
} else {
if (x.right == null) {
x.right = new Node(k);
return;
}
x = x.right;
}
}
}

private void delete(Node x, int k) {
if (x == null)
return;
if (x.key == k) {
x.cnt--;
} else if (k < x.key) {
x.leftSize--;
delete(x.left, k);
} else {
delete(x.right, k);
}
}

private int search(Node x, int n, int presum) {
if (n > x.cnt + x.leftSize + presum)
return search(x.right, n, x.cnt + x.leftSize + presum);
else if (n > x.leftSize + presum)
return x.key;
else
return search(x.left, n, presum);
}
public static void main(String[] args) {
SlidingWindowMedian_480 s = new SlidingWindowMedian_480();
s.medianSlidingWindow(
new int[] {1,3,-1,-3,5,3,6,7}, 3);
}```

0 条评论

• ### leetcode363. Max Sum of Rectangle No Larger Than K

现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少? 注：后面的文章中将使用[左上角顶点坐标...

• ### 395. Longest Substring with At Least K Repeating Characters

这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元...

• ### leetcode502. IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

• ### Array - 164. Maximum Gap

Given an unsorted array, find the maximum difference between the successive elem...

• ### 微信会被封？！包子 Leetcode 1512 solution Number of Good Pairs

包子君讲解的leetcode题目是越来越简单，在标题党的路上确实越走越远，对不起包子粉了?

• ### 洛谷P3355 骑士共存问题

题目描述 在一个 n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入 ? 对于给定的 n*n 个方格的国...

• ### LeetCode 477 Total Hamming Distance

The Hamming distance between two integers is the number of positions at which th...

• ### 算法篇：求1的个数

https://leetcode-cn.com/problems/number-of-1-bits/

• ### 51Nod-1637-幸运数字转换

ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <queue> using namespace...