0295-find-median-from-data-stream.go

typeIntHeap []int
func (hIntHeap) Len() int { returnlen(h) }
func (hIntHeap) Less(i, jint) bool { returnh[i] <h[j] }
func (hIntHeap) Swap(i, jint) { h[i], h[j] =h[j], h[i] }
func (h*IntHeap) Push(xinterface{}) {*h=append(*h, x.(int))}
func (h*IntHeap) Pop() interface{} {
old:=*h
n:=len(old)
x:=old[n-1]
*h=old[0 : n-1]
returnx
}

typeMedianFinderstruct {
smallIntHeap
largeIntHeap
}


funcConstructor() MedianFinder {
returnMedianFinder{small: IntHeap{}, large: IntHeap{}}
}


func (this*MedianFinder) AddNum(numint) {
iflen(this.large) >0&&num>this.large[0] {
heap.Push(&this.large, num)
 } else {
heap.Push(&this.small, -1*num)
 }

iflen(this.small) >len(this.large) +1 {
val:=-1*heap.Pop(&this.small).(int)
heap.Push(&this.large, val)
 }
iflen(this.large) >len(this.small) +1 {
val:=heap.Pop(&this.large).(int)
heap.Push(&this.small, -1*val)
 }
}


func (this*MedianFinder) FindMedian() float64 {
iflen(this.small) >len(this.large) {
returnfloat64(-1*this.small[0])
 } elseiflen(this.large) >len(this.small) {
returnfloat64(this.large[0])
 }
returnfloat64(-1*this.small[0] +this.large[0]) /2
}