数据流的中位数 - 堆（优先队列）
// minHeap 中的数的数量比 maxHeap 多一个
type MedianFinder struct {
minHeap, maxHeap MyHeap
}
func Constructor() MedianFinder {
return MedianFinder{}
}
func (this *MedianFinder) AddNum(num int) {
minHeap, maxHeap := &this.minHeap, &this.maxHeap
if minHeap.Len() == 0 || num <= -minHeap.IntSlice[0] {
heap.Push(minHeap, -num)
if maxHeap.Len() + 1 < minHeap.Len() {
heap.Push(maxHeap, -heap.Pop(minHeap).(int))
}
} else {
heap.Push(maxHeap, num)
if minHeap.Len() < maxHeap.Len() {
heap.Push(minHeap, -heap.Pop(maxHeap).(int))
}
}
}
func (this *MedianFinder) FindMedian() float64 {
minHeap, maxHeap := this.minHeap, this.maxHeap
if (minHeap.Len() + maxHeap.Len()) & 1 == 0 {
return float64(maxHeap.IntSlice[0]-minHeap.IntSlice[0]) / 2
} else {
return float64(-minHeap.IntSlice[0])
}
}
type MyHeap struct { sort.IntSlice }
func (h *MyHeap) Push(v interface{}) {
h.IntSlice = append(h.IntSlice, v.(int))
}
func (h *MyHeap) Pop() interface{} {
n := len(h.IntSlice)
res := h.IntSlice[n - 1]
h.IntSlice = h.IntSlice[:n - 1]
return res
}
/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(num);
* param_2 := obj.FindMedian();
*/
数据流的中位数 - 有序集合 + 双指针
type MedianFinder struct {
nums *redblacktree.Tree
size int
left, right iterator
}
func Constructor() MedianFinder {
return MedianFinder{ nums: redblacktree.NewWithIntComparator() }
}
func (this *MedianFinder) AddNum(num int) {
if count, has := this.nums.Get(num); has {
this.nums.Put(num, count.(int) + 1)
} else {
this.nums.Put(num, 1)
}
if this.size == 0 {
it := this.nums.Iterator()
it.Next()
this.left = iterator{ it, 1 }
this.right = this.left
} else if this.size & 1 == 1 {
if num < this.left.Key().(int) {
this.left.prev()
} else {
this.right.next()
}
} else {
if this.left.Key().(int) < num && num < this.right.Key().(int) {
this.left.next()
this.right.prev()
} else if num >= this.right.Key().(int) {
this.left.next()
} else {
this.right.prev()
this.left = this.right
}
}
this.size++
}
func (this *MedianFinder) FindMedian() float64 {
return float64(this.left.Key().(int) + this.right.Key().(int)) / 2
}
type iterator struct {
redblacktree.Iterator
count int
}
func (it *iterator) prev() {
if it.count > 1 {
it.count--
} else {
it.Prev()
it.count = it.Value().(int)
}
}
func (it *iterator) next() {
if it.count < it.Value().(int) {
it.count++
} else {
it.Next()
it.count = 1
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(num);
* param_2 := obj.FindMedian();
*/