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  // @Title: 数据流中的中位数 (数据流中的中位数 LCOF) // @Author: 15816537946@163.com // @Date: 2022-02-20 15:05:52 // @Runtime: 80 ms // @Memory: 13.6 MB import "container/heap" type IntHeap []int func (h IntHeap) Len() int { return len(h)} func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntHeap) Swap(i,j int) {h[i],h[j] = h[j],h[i]} func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { old:= *h n := len(old) x := old[n-1] *h = old[:n-1] return x } type MedianFinder struct { large, small *IntHeap } /** initialize your data structure here. */ func Constructor() MedianFinder { a := &IntHeap{} b := &IntHeap{} heap.Init(a) heap.Init(b) return MedianFinder{a,b} } func (this *MedianFinder) AddNum(num int) { if this.large.Len() == 0 || num > (*this.large)[0] { heap.Push(this.large,num) } else { heap.Push(this.small,-num) } // 调节大小栈，确保 FindMedian() 得到正确的结果 if this.large.Len() > this.small.Len() +1 { heap.Push(this.small,-heap.Pop(this.large).(int)) } else if this.small.Len() > this.large.Len() +1 { heap.Push(this.large,-heap.Pop(this.small).(int)) } } func (this *MedianFinder) FindMedian() float64 { if this.large.Len() < this.small.Len() { return float64(-(*this.small)[0]) } else if this.large.Len() > this.small.Len() { return float64((*this.large)[0]) } return float64(-(*this.small)[0]+(*this.large)[0])/2 } /** * Your MedianFinder object will be instantiated and called as such: * obj := Constructor(); * obj.AddNum(num); * param_2 := obj.FindMedian(); */