友情支持
如果您觉得这个笔记对您有所帮助，看在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. 数据流的中位数 中的 Two Heaps 对顶堆 在“运动”中，删除，添加，求中位数。
直接使用对顶堆会超时！加上延迟删除技巧，就可以通过。所谓延迟删除技巧，就是只删除堆顶，其余只做删除标记。这样，就不用耗时去堆里遍历查找要删除的元素。
-
一刷（超时）
-
二刷（超时）
-
三刷
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;
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-16 22:41:00
*/
public double[] medianSlidingWindow(int[] nums, int k) {
List<Double> result = new ArrayList<>();
MedianFinder finder = new MedianFinder();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
finder.addNum(num);
if (finder.size() < k) {
continue;
}
result.add(finder.findMedian());
int deleted = nums[i - k + 1];
finder.deleteNum(deleted);
}
return result.stream().mapToDouble(i -> i).toArray();
}
private static class MedianFinder {
private final PriorityQueue<Integer> topSmallHeap;
private final PriorityQueue<Integer> topLargeHeap;
private int topSmallSize;
private int topLargeSize;
private Map<Integer, Integer> waitDelateNum;
public MedianFinder() {
topSmallHeap = new PriorityQueue<>();
topSmallSize = 0;
topLargeHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
topLargeSize = 0;
waitDelateNum = new HashMap<>();
}
public void addNum(int num) {
if (Objects.equals(topSmallSize, topLargeSize)) {
deleteTop(topLargeHeap);
topLargeHeap.offer(num);
topSmallHeap.offer(topLargeHeap.poll());
topSmallSize++;
} else {
deleteTop(topSmallHeap);
topSmallHeap.offer(num);
topLargeHeap.offer(topSmallHeap.poll());
topLargeSize++;
}
}
public void deleteNum(int num) {
if (!topLargeHeap.isEmpty() && num <= topLargeHeap.peek()) {
waitDelateNum.put(num, waitDelateNum.getOrDefault(num, 0) + 1);
deleteTop(topLargeHeap);
topLargeSize--;
} else if (!topSmallHeap.isEmpty() && num >= topSmallHeap.peek()) {
waitDelateNum.put(num, waitDelateNum.getOrDefault(num, 0) + 1);
deleteTop(topSmallHeap);
topSmallSize--;
}
if (topLargeSize > topSmallSize) {
deleteTop(topLargeHeap);
topSmallHeap.offer(topLargeHeap.poll());
topLargeSize--;
topSmallSize++;
}
if (topSmallSize - topLargeSize > 1) {
deleteTop(topSmallHeap);
topLargeHeap.offer(topSmallHeap.poll());
topSmallSize--;
topLargeSize++;
}
}
public double findMedian() {
if (Objects.equals(topSmallSize, topLargeSize)) {
deleteTop(topSmallHeap);
deleteTop(topLargeHeap);
return (0.0D + topLargeHeap.peek() + topSmallHeap.peek()) / 2.0;
} else {
deleteTop(topSmallHeap);
return topSmallHeap.peek();
}
}
public int size() {
return topSmallHeap.size() + topLargeHeap.size();
}
private void deleteTop(PriorityQueue<Integer> queue) {
while (!queue.isEmpty() && waitDelateNum.getOrDefault(queue.peek(), 0) > 0) {
int deleted = queue.poll();
waitDelateNum.put(deleted, waitDelateNum.get(deleted) - 1);
}
}
}