Leetcode 295 Find Median from Data Stream

Find Median from Data Stream

原题

解答思路

本题涉及到一个比较重要且常见的问题，如何动态的去维护数组的中位数？

对于这个问题，既可以用红黑树来解决，也可以用堆来解决。但前者维护起来比较复杂，后者更加简单易用，所以我们通常采用堆来解决。

中位数能够将数组分为两部分，本题的突破口也正在于此，假设中位数将当前数组划分为了L[0:l]和R[r:n]两个部分，并且以递增的情况来处理这一问题。那么显然中位数就是在L的末尾处和R的开头处，即L中的最大元素和R中的最小元素，显然我们可以用一个大根堆和一个小根堆来解决这一问题。

如何找到中位数？

考虑到数组长度会有奇偶两种情况，长度为偶数时，我们可以直接用上述两个元素求平均数即可；长度为奇数时，中位数是当前划分L和R的那个元素。从方便的角度来看，我们可以把这个中位数暂存在L中，这样的话，只需要保证L的长度要么是等于R的长度（偶数情况），要么是R的长度+1（奇数情况）。

如何动态维护？

基于上面确认中位数的方法，我们就需要考虑如何动态地维护这两个堆。首先是当两个堆都为空的时候，就需要先将数据压入到左半部分的大根堆中。若堆不为空，就判定当前数据和左半部分大根堆的最大元素之间的关系，如果比左半部分的堆顶要小，说明该元素还是归属于左半部分的，否则就归入右半部分。

归入后，需要我们去动态地调整两个堆来保证其始终能够将数组分为符合要求的两部分：

归入左半部分后，检查当前Len(leftPart)是否大于Len(rightPart)+1，若大于，则需要将左半部分大根堆的堆顶元素移动到右半部分
归入右半部分后，检查当前Len(rightPart)是否大于Len(leftPart)，若大于，则需要将右半部分小根堆的堆顶元素移动到左半部分

需要考虑的细节问题？

1. 如何构建大根堆和小根堆？

为了构建起来比较方便，我们不希望为两个堆结构都去单独声明一个结构体。因此可以只声明构建一个基于sort.IntSlice的小根堆，可以靠向其中压入数据的相反数来构建相应的大根堆。

2. 如何确定中位数的位置

通过判断左半部分和右半部分的长度即可，因为我们默认中位数被存储在左半部分的堆里。若两部分的长度相等，则说明当前数组是偶数，中位数就是两个堆顶元素的平均数；否则，中位数就是左半部分的堆顶元素。

代码

type myHeap struct {
    sort.IntSlice
}

func (h *myHeap) Push(x interface{}) {
    h.IntSlice = append(h.IntSlice, x.(int))
}

func (h *myHeap) Pop() interface{} {
    old := h.IntSlice
    n := len(old)
    x := old[n-1]
    h.IntSlice = old[:n-1]
    return x
}

type MedianFinder struct {
    maxHeap myHeap  // 左半部分：大根堆（通过填入负数实现）
    minHeap myHeap  // 右半部分：小根堆
}


func Constructor() MedianFinder {
    return MedianFinder{}
}


func (this *MedianFinder) AddNum(num int)  {
    leftQue, rightQue := &this.maxHeap, &this.minHeap
    if leftQue.Len() == 0 || num < -leftQue.IntSlice[0] {
        heap.Push(leftQue, -num)
        
        if leftQue.Len() > rightQue.Len() + 1 {
            heap.Push(rightQue, -heap.Pop(leftQue).(int))
        }

    } else {
        heap.Push(rightQue, num)
        
        if rightQue.Len() > leftQue.Len() {
            heap.Push(leftQue, -heap.Pop(rightQue).(int))
        }
    }   
}


func (this *MedianFinder) FindMedian() float64 {
    leftQue, rightQue := this.maxHeap, this.minHeap
    if leftQue.Len() != rightQue.Len() {
        return float64( -leftQue.IntSlice[0] )
    } else {
        return float64( -leftQue.IntSlice[0] + rightQue.IntSlice[0] ) / 2.0
    }
}


/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */

关于golang中的堆构建

Q: 我们注意到一个问题，myHeap结构体中使用的是sort.IntSlice，它是默认递增的，构建出来的堆就是小根堆，IntSlice[0]就是小根堆的堆顶，但是，Pop()里面n:= len(h.IntSlice)，那么x = h.IntSlice[n-1]就不是堆顶，可是Pop()操作不应该是要弹出堆顶吗？这样操作为什么是正确的？

A: 这里的关键在于 Go 的 heap 包的工作机制。当你调用 heap.Pop(h) 时，它不会直接调用你实现的 Pop() 方法，而是会：

先交换第一个和最后一个元素
然后调整堆结构
最后才调用你实现的 Pop() 方法来移除最后一个元素

heap.Pop 的实际实现（简化版）：

func Pop(h Interface) interface{} {
    n := h.Len() - 1
    h.Swap(0, n)        // 将堆顶与最后一个元素交换
    down(h, 0, n)       // 调整堆
    return h.Pop()      // 调用用户实现的 Pop，此时移除的是原来的堆顶
}

当调用 heap.Pop(&h) 时：

heap.Pop 内部先将 h.IntSlice[0]（堆顶）与 h.IntSlice[n-1]（最后一个元素）交换
然后进行堆调整，确保堆性质
最后调用你的 Pop() 方法，此时：old[n-1] 实际上是原来的堆顶元素

大根堆与小根堆

原题

解答思路

如何找到中位数？

如何动态维护？

需要考虑的细节问题？

代码

关于golang中的堆构建

CATALOG

FEATURED TAGS