295. 数据流的中位数

用时 : 看了答案

既然是堆的练习,肯定是往堆的思路去靠拢了

由于我们要的仅仅是中位数,其实没有必要把所有的数都排序

可以用两个堆,一个最大堆一个最小堆

当总数为单数(即 最大堆 - 最小堆 个数 = 1),拿到最大堆的最大值

当总数为双数(即最大堆个数 = 最小堆) ,拿到最大堆最大值和最小堆最小值

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
const swap = function (arr,i,j) {
[arr[i],arr[j]] = [arr[j],arr[i]]
}

class Heap {
constructor() {
this.count = 0
this.data = new Array(this.count + 1)
}
shiftUp(k) {
// 把新的元素往上排
while(k>=1) {
let father = Math.floor(k / 2)
if (this.data[k] > this.data[father]) {
swap(this.data,k,father)
k = father
} else {
break
}
}
}
shiftDown(k) {
while( k * 2 <= this.count) { // 表示k 有孩子
let j = k
if (k * 2 + 1 <= this.count && this.data[k * 2 + 1] > this.data[k] && this.data[k * 2 + 1] > this.data[k * 2]) {
j = k * 2 + 1
} else if (this.data[k * 2] > this.data[k]) {
j = k * 2
} else {
break
}
swap(this.data,j,k)
k = j
}
}
size() {
return this.count
}
isEmpty() {
return this.count === 0
}
insert(item) {
this.data[++this.count] = item
this.shiftUp(this.count)
}
extractMax() {
if (this.count <= 0) return
let ret = this.data[1]
swap(this.data,1,this.count--)
this.shiftDown(1)
return ret
}
}


var MedianFinder = function() {
this.maxHeap = new Heap();
this.minHeap = new Heap();
};

MedianFinder.prototype.addNum = function(num) {
//[1] []
// [1,2] [] -> [1] [2]
// [1,3] [2] -> [1,2] [3]
// [1,2,4] [3] -> [1,2] [3,4]
// [1,2,5] [3,4] -> [1,2,4] [4,5]
var maxHeapsize = this.maxHeap.size()
var minHeapsize = this.minHeap.size()
this.maxHeap.insert(num)
var max = this.maxHeap.extractMax()
this.minHeap.insert(-max )
if (maxHeapsize === minHeapsize) {
var min = Math.abs(this.minHeap.extractMax())
this.maxHeap.insert(min)
}
};

MedianFinder.prototype.findMedian = function() {
if (this.maxHeap.size() === this.minHeap.size()) {
var max = this.maxHeap.extractMax()
var min = Math.abs(this.minHeap.extractMax())
return (max + min) / 2
} else {
return this.maxHeap.extractMax()
}
};

需要注意的点

  1. 为了保证最大堆 个数 - 最小堆 为 0 ~ 1,且最大堆的最大值 < 最小堆 的最小值,每次数先进入最大堆,然后最大堆把最大值传递给最小堆。再根据数量判断是否把最小堆的最小值给最大堆
  2. 只实现了最大堆,但是可以用负数来做最小堆,出的时候别忘了也要负数