41.md

数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

进阶：空间复杂度是 O(n)， 时间复杂度是 O(nlogn)

示例

输入：[5,2,3,4,1,6,7,0,8]

返回值："5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

说明：数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...

思路

• 插入时排序，而不是读取时排序
• 数据流，一边插入一边排序，不就是插入排序

实现

var data []int

func Insert(num int) {
	if len(data) == 0 {
		data = append(data, num)
		return
	}
	for v := 0; v < len(data); v++ {
		if num < data[v] {
			num, data[v] = data[v], num
		}
	}
	data = append(data, num)
}

func GetMedian() float64 {
	length := len(data)
	if length == 0 {
		return -1
	}
	if length%2 == 0 {
		return float64(data[length/2-1]+data[length/2]) / 2
	} else {
		return float64(data[length/2])
	}
}