数据流的中位数

yczha大约 3 分钟

题目表述

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

解题思路

求中位数，避免不了需要用一个容器将流入的数据保存起来，那么选择什么容器比较合适呢？

1）数组

最简单的容器。如果是未排序的数组，找中位数的方法采用快排。因此，插入时间复杂度是 $O (1)$ ，而找中位数的时间复杂度是 $O (n l o g (n))$ 。

如果是排序的数组，由于是流式数据，适合使用插入排序。因此，插入的时间复杂度是 $O (n)$ ，而找中位数的时间复杂度是 $O (1)$ 。

2）链表

由于数组使用插入排序，每次都需要进行大量的位移操作和扩容操作，故此可使用链表取代。排序的链表，插入的时间复杂度还是 $O (n)$ ，找中位数的时间复杂度是 $O (n)$

3）二叉搜索树

使用二叉搜索树，可以将插入的时间复杂度降至 $O (l o g (n))$ ；而找到中位数的时间复杂度是但二叉搜索树有可能退化成一个链表，此时插入的时间复杂度是 $O (n)$ 。

4）AVL

将普通的二叉搜索树改进成平衡二叉树（AVL），再将左右子树深度只差 1 个单位，这样插入数据的时间复杂度是 $O (l o g (n))$ ，找到中位数的时间复杂度是 $O (1)$ 。

5）一个大顶堆+一个小顶堆【推荐】

核心思想： 中位数左边的数据（左边数据特点是都不大于中位数）保存在大顶堆中，中位数右边的数据（右边数据特点是都不小于中位数）保存在小顶堆中。【关键在于保持两个堆保存的数据个数相等或只差一个】

根据堆的插入，插入数据的时间复杂度是 $O (l o g (n))$ 。而中位数肯定在两个堆的堆顶元素中，找到中位数的时间复杂度是 $O (1)$ 。

关键点：

中位数左边的数据保存在大顶堆；中位数右边的数据保存在小顶堆中。
始终保持两个堆保存的数据个数相等或者只差一个。

实现思路：

当输入数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；
当输入数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；
取中位数的时候，如果当输入数目为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当输入数目为奇数，显然是取小顶堆的根节点

代码实现：

import heapq
from typing import List


def findMiddle(nums: List[int]) -> float:
    """找到数据流的中位数
    Python中的堆默认是小顶堆，通过转为负数实现大顶堆
    """
    # 初始化堆
    top, bottom = [], []
    heapq.heapify(top)
    heapq.heapify(bottom)
    # 遍历元素
    for i, v in enumerate(nums):
        if (i + 1) % 2 == 0:
            # 元素入堆
            heapq.heappush(top, -v)
            # 取出堆顶元素加入小顶堆
            t = -heapq.heappop(top)
            heapq.heappush(bottom, t)
        else:
            heapq.heappush(bottom, v)
            # 取出堆顶元素加入大顶堆
            b = heapq.heappop(bottom)
            heapq.heappush(top, -b)
    if len(nums) % 2 == 0:
        return (-heapq.heappop(top) + heapq.heappop(bottom)) / 2
    return -heapq.heappop(top)


if __name__ == "__main__":
    mid = findMiddle([1, 5, 2, 8, 4, 3])
    print(f"mid value is {mid}")

package main

import (
	"container/heap"
	"fmt"
)

// 构建堆
type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	last := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return last
}

// 找到数据流的中位数
func findMiddle(nums []int) float64 {
	// 初始化堆
	top := &IntHeap{}
	bottom := &IntHeap{}
	heap.Init(top)
	heap.Init(bottom)
	// 遍历元素
	for i, v := range nums {
		if (i+1)%2 == 0 {
			// 元素入堆
			heap.Push(top, -v)
			// 取出堆顶元素加入小顶堆
			heap.Push(bottom, -heap.Pop(top).(int))
		} else {
			heap.Push(bottom, v)
			// 取出堆顶元素加入大顶堆
			heap.Push(top, -heap.Pop(bottom).(int))
		}
	}
	if len(nums)%2 == 0 {
		return float64(-heap.Pop(top).(int)+heap.Pop(bottom).(int)) / 2.0
	}
	return float64(-heap.Pop(top).(int))
}

func main() {
	nums := []int{1, 5, 2, 8, 4, 3, 6}
	mid := findMiddle(nums)
	fmt.Println("Mid is", mid)
}

数据流的中位数

# 题目表述

# 解题思路

# 1）数组

# 2）链表

# 3）二叉搜索树

# 4）AVL

# 5）一个大顶堆+一个小顶堆【推荐】