刷题使我快乐，满脸开心.jpg

  • 来源：力扣（LeetCode）
  • 链接：https://leetcode.cn/problems/find-median-from-data-stream/
  • 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -10^5 <= num <= 10^5
  • 在调用 findMedian 之前，数据结构中至少有一个元素
  • 最多 5 * 10^4 次调用 addNum 和 findMedian

思路

首先堵个路，全排序，然后找中间数字会超时，别问我为啥知道。。。

那转换下思路，既然排序不行，但是显然需要类似排序的思路，再找中位数会比较方便，于是会有两个想法

  • 堆，堆的插入和弹出时间为 O(n) , 我们可以利用这一点，既然中位数是中间位置的数，或者两数平均，那么我们就用两个堆
    • 小顶堆存较大元素，堆顶就是中间位置较大的数
    • 大顶堆存较小元素，堆顶就是中间位置较小的数
    • 至于中间一个数的场景，选择一个可以存比对方多一个数字即可
  • 既然后排序不行，那就从开始插入时就一个个按位置放好。
    • 放入数字时用二分法插入，然后找中间位置，算中位数
    • 这个方法听起来其实简单很多，但是时间上其实比第一算法要差些, 二分 O(n)，堆插入 O(logn)

双堆

这里我用的第一个办法，下面就是具体实现了

AddNum()

这个函数的目的就是把数字放好，并保证两个堆的堆顶恰好是中间位置的数字
假设我想让小根堆（放较大数字）可以多一个元素

  • 那就开始没有元素直接放小根堆
  • 如果两个堆元素数相同，那就应该是往小根堆放，但是新的数字不一定是中间位置的数字，所以需要先放入大根堆，然后把较小元素中最大的那一个放入小根堆
  • 同理，如果两个堆元素数不同，那就先放小根堆，然后把较大元素中最小的放入大根堆
FindMedian()

在 AddNum() 函数已经完成了中位数寻找的前提下，这里只需要看两个堆元素数是否相同即可

  • 相同则两个堆顶直接求平均
  • 不同则直接拿小根堆堆顶（前提是在小根堆多放一个元素）

二分法相对实现简单，就不搞了，上代码

话说go的堆实现真麻烦哦，看看别人家语言
不过堆排也确实是比较常考的，建议还是会手撸比较好
MySQL limit 实现中，会用到堆排序

代码

type MinHeap []int

func (hp MinHeap) Len() int           { return len(hp) }
func (hp MinHeap) Less(i, j int) bool { return hp[i] < hp[j] }
func (hp MinHeap) Swap(i, j int)      { hp[i], hp[j] = hp[j], hp[i] }

func (hp *MinHeap) Push(x interface{}) {
	*hp = append(*hp, x.(int))
}

func (hp *MinHeap) Pop() interface{} {
	n := len(*hp)
	x := (*hp)[n-1]
	*hp = (*hp)[:n-1]
	return x
}

type MaxHeap []int

func (hp MaxHeap) Len() int           { return len(hp) }
func (hp MaxHeap) Less(i, j int) bool { return hp[i] > hp[j] }
func (hp MaxHeap) Swap(i, j int)      { hp[i], hp[j] = hp[j], hp[i] }

func (hp *MaxHeap) Push(x interface{}) {
	*hp = append(*hp, x.(int))
}

func (hp *MaxHeap) Pop() interface{} {
	n := len(*hp)
	x := (*hp)[n-1]
	*hp = (*hp)[:n-1]
	return x
}

type MedianFinder struct {
	// 小根堆维护较大元素
	minhp *MinHeap
	// 大根堆维护较小元素
	maxhp *MaxHeap
	// 这样设置，缩小了每个堆的处理时间，并且使得中位数很容易取得
	// 我们不妨让小根堆保持比大根堆多一个元素，或者元素个数相等，
	// 那么
	// 如果最终小根堆数量多1，也就是小根堆堆顶就是中位数
	// 如果最终小根堆与大根堆元素数相同，那么中位数就是两个堆的堆顶的平均数
}

func Constructor() MedianFinder {
	return MedianFinder{&MinHeap{}, &MaxHeap{}}
}

func (this *MedianFinder) AddNum(num int) {
	// 如果是空的直接往小根堆放（存放较大元素）
	if this.minhp.Len() == 0 {
		heap.Push(this.minhp, num)
		return
	}
	// 小根堆数量多，需要往大根堆放一个，那就将小根堆的堆顶放过去
	// 才能保证大根堆只放较小元素
	if this.minhp.Len() > this.maxhp.Len() {
		heap.Push(this.minhp, num)
		heap.Push(this.maxhp, heap.Pop(this.minhp).(int))
	} else {
		// 一样多时应往小根堆放，但是需要将大根堆堆顶放过去
		// 才能保证小根堆只放较大元素
		heap.Push(this.maxhp, num)
		heap.Push(this.minhp, heap.Pop(this.maxhp).(int))
	}
}

func (this *MedianFinder) FindMedian() float64 {
	if this.minhp.Len() > this.maxhp.Len() {
		return float64((*this.minhp)[0])
	} else {
		return float64((*this.minhp)[0]+(*this.maxhp)[0]) / 2
	}
}