剑指offer面试题41：数据流中的中位数（golang实现）

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[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 次调用。

算法分析

• 用一对大小堆来存储数据，大根堆中存储较小的一半数据，小根堆中存储较大的一半数据，中位数可以由两个堆的堆顶元素得来。

//	数据结构
type MedianFinder struct {
	minH *minHeap
	maxH *maxHeap
}

minH.Len() == maxH.Len()minH.Len() ！= maxH.Len()minH.Len() == maxH.Len()

复杂度分析

问题规模为数据流中元素的个数n。

• 时间复杂度：O( l o g n logn logn)，维护大根堆/小根堆需要 l o g n logn logn的时间，查找堆顶元素只需要O( 1 1 1)时间。
• 空间复杂度：O( n n n)，需要保存数据流中所有元素。

Golang代码如下

type maxHeap []int
type minHeap []int

func (m maxHeap) Len() int {
	return len(m)
}
func (m minHeap) Len() int {
	return len(m)
}

func (m maxHeap) Less(i, j int) bool {
	return m[i] > m[j]
}
func (m minHeap) Less(i, j int) bool {
	return m[i] < m[j]
}

func (m *maxHeap) Swap(i, j int) {
	(*m)[i], (*m)[j] = (*m)[j], (*m)[i]
}
func (m *minHeap) Swap(i, j int) {
	(*m)[i], (*m)[j] = (*m)[j], (*m)[i]
}

func (m *maxHeap) Push(v interface{}) {
	*m = append(*m, v.(int))
}
func (m *minHeap) Push(v interface{}) {
	*m = append(*m, v.(int))
}

func (m *maxHeap) Pop() interface{} {
	v := (*m)[len(*m)-1]
	*m = (*m)[:len(*m)-1]
	return v
}
func (m *minHeap) Pop() interface{} {
	v := (*m)[len(*m)-1]
	*m = (*m)[:len(*m)-1]
	return v
}

func (m *maxHeap) Max() int {
	return (*m)[0]
}
func (m *minHeap) Min() int {
	return (*m)[0]
}

type MedianFinder struct {
	minH *minHeap
	maxH *maxHeap
}

func Constructor() MedianFinder {
	return MedianFinder{
		new(minHeap),
		new(maxHeap),
	}
}

func (this *MedianFinder) AddNum(num int)  {
	if this.maxH.Len() == this.minH.Len() {
		heap.Push(this.maxH, num)
		heap.Push(this.minH, heap.Pop(this.maxH))
	} else {
		heap.Push(this.minH, num)
		heap.Push(this.maxH, heap.Pop(this.minH))
	}
}

func (this *MedianFinder) FindMedian() float64 {
	if this.minH.Len() == this.maxH.Len() {
		return (float64(this.minH.Min()) + float64(this.maxH.Max())) / 2
	} else {
		return float64(this.minH.Min())
	}
}