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
98
99
| // @Title: 滑动窗口中位数 (Sliding Window Median)
// @Author: 15816537946@163.com
// @Date: 2021-02-03 23:22:27
// @Runtime: 40 ms
// @Memory: 6.6 MB
type hp struct {
sort.IntSlice
size int
}
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
func (h *hp) push(v int) { h.size++; heap.Push(h, v) }
func (h *hp) pop() int { h.size--; return heap.Pop(h).(int) }
func (h *hp) prune() {
for h.Len() > 0 {
num := h.IntSlice[0]
if h == small {
num = -num
}
if d, has := delayed[num]; has {
if d > 1 {
delayed[num]--
} else {
delete(delayed, num)
}
heap.Pop(h)
} else {
break
}
}
}
var delayed map[int]int
var small, large *hp
func medianSlidingWindow(nums []int, k int) []float64 {
delayed = map[int]int{} // 哈希表,记录「延迟删除」的元素,key 为元素,value 为需要删除的次数
small = &hp{} // 大根堆,维护较小的一半元素
large = &hp{} // 小根堆,维护较大的一半元素
makeBalance := func() {
// 调整 small 和 large 中的元素个数,使得二者的元素个数满足要求
if small.size > large.size+1 { // small 比 large 元素多 2 个
large.push(-small.pop())
small.prune() // small 堆顶元素被移除,需要进行 prune
} else if small.size < large.size { // large 比 small 元素多 1 个
small.push(-large.pop())
large.prune() // large 堆顶元素被移除,需要进行 prune
}
}
insert := func(num int) {
if small.Len() == 0 || num <= -small.IntSlice[0] {
small.push(-num)
} else {
large.push(num)
}
makeBalance()
}
erase := func(num int) {
delayed[num]++
if num <= -small.IntSlice[0] {
small.size--
if num == -small.IntSlice[0] {
small.prune()
}
} else {
large.size--
if num == large.IntSlice[0] {
large.prune()
}
}
makeBalance()
}
getMedian := func() float64 {
if k&1 > 0 {
return float64(-small.IntSlice[0])
}
return float64(-small.IntSlice[0]+large.IntSlice[0]) / 2
}
for _, num := range nums[:k] {
insert(num)
}
n := len(nums)
ans := make([]float64, 1, n-k+1)
ans[0] = getMedian()
for i := k; i < n; i++ {
insert(nums[i])
erase(nums[i-k])
ans = append(ans, getMedian())
}
return ans
}
|