如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
最多会对 addNum、findMedian 进行 50000 次调用
解题思路
1，维护一个大根堆和一个小根堆
2，大根堆比小根堆长度大1或者相等
3，如果相等，先插入小根堆，弹出小根堆队首元素，插入大根堆
4，如果不等，先插入大根堆，弹出大根堆队首元素，插入小根堆
5，最后取队首元素的平均值或者长度更长的队首元素
代码实现
代码语言：javascript复制
type heap struct{
data []int
big bool
}
type MedianFinder struct {
Little,Big *heap
}
func (h*heap)Hipfy(i int){
l:=2*i 1
r:=2*i 2
max:=i
if l<len(h.data) && h.Compare(l,max){
max=l
}
if r<len(h.data) && h.Compare(r,max){
max=r
}
if max!=i{
h.data[max],h.data[i]=h.data[i],h.data[max]
h.Hipfy(max)
}
}
func (h*heap)Compare(i,j int)bool{
if h.big{
return h.data[i]>h.data[j]
}
return h.data[i]<h.data[j]
}
func (h*heap)Insert(i int){
h.data=append(h.data,i)
for i:=len(h.data)/2;i>=0;i--{
h.Hipfy(i)
}
}
func (h*heap)Pop()int{
if len(h.data)<1{
return -1
}
v:=h.data[0]
h.data[0]=h.data[len(h.data)-1]
h.data=h.data[:len(h.data)-1]
h.Hipfy(0)
return v
}
/** initialize your data structure here. */
func Constructor() MedianFinder {
return MedianFinder{
Little:&heap{},
Big:&heap{big:true},
}
}
func (this *MedianFinder) AddNum(num int) {
if len(this.Little.data)==len(this.Big.data){
this.Little.Insert(num)
v:=this.Little.Pop()
this.Big.Insert(v)
return
}
this.Big.Insert(num)
this.Little.Insert(this.Big.Pop())
}
func (this *MedianFinder) FindMedian() float64 {
if len(this.Little.data)<len(this.Big.data){
return float64(this.Big.data[0])
}
return float64(this.Big.data[0] this.Little.data[0])/2.0
}
/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(num);
* param_2 := obj.FindMedian();
*/
