中位数是有序序列最中间的那个数。
如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。
例如:
[2,3,4]
,中位数是 3
[2,3]
,中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums,有一个长度为 k 的窗口从最左端滑动到最右端。
窗口中有 k 个数,每次窗口向右移动 1 位。
你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。
示例:
给出 nums = [1,3,-1,-3,5,3,6,7]
,以及 k = 3。
窗口位置 中位数
--------------- -----
[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
提示:
以内的答案将被视作正确答案。
一个直观的做法是:对每个滑动窗口的数进行排序,获取排序好的数组中的第 k / 2
和 (k - 1) / 2
个数(避免奇偶数讨论),计算中位数。
我们大概分析就知道这个做法至少
的,算上排序的话应该是
。
比较无奈的是,这道题不太正规,没有给出数据范围。我们无法根据判断这样的做法会不会超时。
PS. 实际上这道题朴素解法是可以过的,有蓝桥杯内味了 ~
朴素做法通常是优化的开始,所以我还是提供一下朴素做法的代码:
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length;
int cnt = n - k + 1;
double[] ans = new double[cnt];
int[] tmp = new int[k];
for (int l = 0, r = l + k - 1; r < n; l++, r++) {
for (int i = l; i <= r; i++) tmp[i - l] = nums[i];
Arrays.sort(tmp);
ans[l] = (tmp[k / 2] / 2.0) + (tmp[(k - 1) / 2] / 2.0);
}
return ans;
}
}
n
个窗口需要滑动计算。每个窗口,需要先插入数据,复杂度为 ,插入后需要排序,复杂度为
。整体复杂度为
。
k
的临时数组。复杂度为 。
从朴素解法中我们可以发现,其实我们需要的就是滑动窗口中的第 k / 2
小的值和第 (k - 1) / 2
小的值。
我们知道滑动窗口求最值的问题,可以使用优先队列来做。
但这里我们求的是第 k
小的数,而且是需要两个值。还能不能使用优先队列来做呢?
我们可以维护两个堆:
(k - 1) / 2
小的值)k / 2
小的值)滑动窗口的中位数就是两个堆的堆顶元素的平均值。
实现细节:
k
个元素直接入 right
,再从 right
中倒出 k / 2
个到 left
中。这时候可以根据 left
和 right
得到第一个滑动窗口的中位值。left.size() == right.size()
或 right.size() - left.size() == 1
,对应了窗口长度为偶数或者奇数的情况)
2.3 根据 left
堆 和 right
堆得到当前滑动窗口的中位值代码:
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length;
int cnt = n - k + 1;
double[] ans = new double[cnt];
// 如果是奇数滑动窗口,让 right 的数量比 left 多一个
// 1.滑动窗口的左半部分
PriorityQueue<Integer> left = new PriorityQueue<>((a,b)->Integer.compare(b,a));
// 2.滑动窗口的右半部分
PriorityQueue<Integer> right = new PriorityQueue<>((a,b)->Integer.compare(a,b));
for (int i = 0; i < k; i++) right.add(nums[i]);
for (int i = 0; i < k / 2; i++) left.add(right.poll());
ans[0] = getMid(left, right);
for (int i = k; i < n; i++) {
// 人为确保了 right 会比 left 多
// 因此,删除和添加都与 right 比较(left 可能为空)
int add = nums[i], del = nums[i - k];
if (add >= right.peek()) {
right.add(add);
} else {
left.add(add);
}
if (del >= right.peek()) {
right.remove(del);
} else {
left.remove(del);
}
adjust(left, right);
ans[i - k + 1] = getMid(left, right);
}
return ans;
}
void adjust(PriorityQueue<Integer> left,
PriorityQueue<Integer> right) {
while (left.size() > right.size())
right.add(left.poll());
while (right.size() - left.size() > 1)
left.add(right.poll());
}
double getMid(PriorityQueue<Integer> left,
PriorityQueue<Integer> right) {
if (left.size() == right.size()) {
return (left.peek() / 2.0) + (right.peek() / 2.0);
} else {
return right.peek() * 1.0;
}
}
}
k
,因此堆操作复杂度为 ;窗口数量最多为 n
。整体复杂度为
。
n
个元素在堆内。复杂度为 。
今天的题解发到 LeetCode 后,针对一些同学的评论。
我觉得有一定的代表性,所以拿出来讲讲 ~
new PriorityQueue<>((x,y)->(y-x))
的写法会有某些案例无法通过?和 new PriorityQueue<>((x,y)->Integer.compare(y,x))
写法有何区别?(x,y)->(y-x)
的写法逻辑没有错,AC 不了是因为 int 溢出。
在 Java 中 Integer.compare 的实现是 (x < y) ? -1 : ((x == y) ? 0 : 1)
。只是单纯的比较,不涉及运算,所以不存在溢出风险。
而直接使用 y - x
,当 y = Integer.MAX_VALUE
, x = Integer.MIN_VALUE
时,到导致溢出,返回的是 负数 ,而不是逻辑期望的 正数同样具有溢出问题的还有计算第 k / 2
小的数和第 (k - 1) / 2
小的数的平均值时。
我是使用 (a / 2.0) + (b / 2.0)
的形式,而不是采用 (a + b) / 2.0
的形式。后者有相加溢出的风险。
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。