友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
480. 滑动窗口中位数
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
-
[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
因此，返回该滑动窗口的中位数数组 `[1,-1,-1,3,5,6]`。
提示：
-
你可以假设
k始终有效，即：k始终小于等于输入的非空数组的元素个数。 -
与真实值误差在
10-5以内的答案将被视作正确答案。
思路分析
利用 295. 数据流的中位数 中的双堆模式在“运动”中，删除，添加，求中位数。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* 答案是正确的，超大数组测试时，超时了。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-08-30 11:45:50
*/
public double[] medianSlidingWindow(int[] nums, int k) {
// 如果窗口是奇数，则 topSmall 多一个
Queue<Integer> topSmall = new PriorityQueue<>((a, b) -> Integer.compare(a, b));
// 使用 Integer.compare，防止两个最小负数相减时溢出
Queue<Integer> topLarge = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
double[] result = new double[nums.length - k + 1];
for (int i = 0; i < k; i++) {
topSmall.add(nums[i]);
}
for (int i = 0; i < k / 2; i++) {
topLarge.add(topSmall.poll());
}
// 先相处再相加，防止溢出
result[0] = k % 2 == 1 ? 1.0 * topSmall.peek()
: topSmall.peek() / 2.0 + topLarge.peek() / 2.0;
for (int i = k; i < nums.length; i++) {
int num = nums[i];
if (topSmall.peek() <= num) {
topSmall.add(num);
} else {
topLarge.add(num);
}
int delNum = nums[i - k];
if (topSmall.peek() <= delNum) {
topSmall.remove(delNum);
} else {
topLarge.remove(delNum);
}
// 添加，删除，再平衡双堆，这样才能保证堆的平衡性
// topSmall 应该始终大于等于 topLarge
while (topLarge.size() > topSmall.size()) {
topSmall.add(topLarge.poll());
}
// topSmall 与 topLarge 的差值不能大于 1
while (topSmall.size() - topLarge.size() > 1) {
topLarge.add(topSmall.poll());
}
result[i - k + 1] = k % 2 == 1 ? 1.0 * topSmall.peek()
: topSmall.peek() / 2.0 + topLarge.peek() / 2.0;
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* 优化前，通过 43 / 44 个测试用例。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-09-15 22:04:02
*/
public double[] medianSlidingWindow(int[] nums, int k) {
PriorityQueue<Integer> topSmall = new PriorityQueue<>();
PriorityQueue<Integer> topLarge = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
double[] result = new double[nums.length - k + 1];
int index = 0;
while (index < nums.length) {
int num = nums[index];
if (topLarge.isEmpty() || topLarge.peek() >= num) {
topLarge.add(num);
} else {
topSmall.add(num);
}
if (k <= index) {
int delete = nums[index - k];
if (delete > topLarge.peek()) {
topSmall.remove(delete);
} else {
topLarge.remove(delete);
}
}
while (topSmall.size() > topLarge.size()) {
topLarge.offer(topSmall.poll());
}
while (topLarge.size() - topSmall.size() > 1) {
topSmall.offer(topLarge.poll());
}
if (topSmall.size() + topLarge.size() == k) {
result[index - k + 1] = getMedian(k, topSmall, topLarge);
}
index++;
}
return result;
}
private static double getMedian(int k, PriorityQueue<Integer> topSmall, PriorityQueue<Integer> topLarge) {
if ((k & 1) == 1) {
return topLarge.peek();
}
return (0D + topSmall.peek() + topLarge.peek()) / 2.0;
}