剑指 41. 数据流中的中位数 难

剑指 Offer 41. 数据流中的中位数

和力扣295. 数据流的中位数 一致
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

**

完美的面试回答，你被录取了：

• 在数据流中，数据会不断涌入结构中，那么也就面临着需要多次动态调整以获得中位数。 因此实现的数据结构需要既需要快速找到中位数，也需要做到快速调整。
• 首先能想到就是二叉搜索树，在平衡状态下，树顶必定是中间数，然后再根据长度的奇偶性决定是否取两个数。
• 此方法效率高，但是手动编写较费时费力。
• 根据只需获得中间数的想法，可以将数据分为左右两边，一边以最大堆的形式实现，可以快速获得左侧最大数， 另一边则以最小堆的形式实现。其中需要注意的一点就是左右侧数据的长度差不能超过1。 这种实现方式的效率与AVL平衡二叉搜索树的效率相近，但编写更快

// 两个堆-大顶~小顶 ；用队列建堆
//时间：删除logn，查找O1；空间On
type MedianFinder struct {
    heapMax *IntHeap1               // 最大堆 -> 代表排序后数据流的左半部分
    heapMin *IntHeap2               // 最小堆 -> 代表排序后数据流的右半部分
}
func Constructor() MedianFinder {
    return MedianFinder{heapMin: &IntHeap2{}, heapMax: &IntHeap1{}}
}
func (this *MedianFinder) AddNum(num int) {
    if (*this.heapMax).Len() == 0 {
        heap.Push(this.heapMax, num)
        return
    }
    m, n := (*this.heapMax).Len(), (*this.heapMin).Len()
    if m == n+1 {
        //1, 因为数据流的长度可能为奇数，所以允许最大堆的数量比最小堆的数量多1
        for num < (*this.heapMax)[0] {
            heap.Push(this.heapMax, num)
            num = heap.Pop(this.heapMax).(int)
        }
        //2, 最大堆的数量已经比最小堆多1，所以num应该加入最小堆
        heap.Push(this.heapMin, num)
    } else {
        for num > (*this.heapMin)[0] {
            heap.Push(this.heapMin, num)
            num = heap.Pop(this.heapMin).(int)
        }
        //3, 加入最大堆
        heap.Push(this.heapMax, num)
    }
}
func (this *MedianFinder) FindMedian() float64 {
    m, n := (*this.heapMax).Len(), (*this.heapMin).Len()
    if m == n { // 如果列表长度是偶数，中位数则是中间两个数的平均值。
        return (float64((*this.heapMax)[0]) + float64((*this.heapMin)[0])) / 2.0
    }
    return float64((*this.heapMax)[0])
}
// 最小堆
type IntHeap2 []int
func (h IntHeap2) Len() int           { return len(h) }
func (h IntHeap2) Less(i, j int) bool { return h[i] < h[j] }            // 就这里不同
func (h IntHeap2) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap2) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *IntHeap2) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
// 最大堆
type IntHeap1 []int
func (h IntHeap1) Len() int           { return len(h) }
func (h IntHeap1) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap1) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap1) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *IntHeap1) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}