JZ41 数据流中的中位数

发表于 分类于 本文字数： 475 阅读时长 ≈ 2 分钟

JZ41 数据流中的中位数

描述

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

数据范围：数据流中数个数满足$1≤n≤1000$ ，大小满足 $1≤val≤1000$

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

示例1 

1
2
3
输入：[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...

示例2

1
2
输入：[1,1,1]
返回值："1.00 1.00 1.00 "

题解

很久没有写题了，这段时间实习有足够的摸鱼时间，终于能把这个小项目收尾了，从这道题开始后续就使用python来写了，人生苦短我选python。

这道题本是对堆的考察，一个大根堆一个小根堆，在插入的过程中平衡二者，这样就可以很便利的去寻找中位数了，这样满足的是进阶的要求。

但是考虑到可以自定义一个插入的过程，那么其实可以直接使用插入排序，插入时就把数组顺序拍好，一样可以做到快捷的中位数寻找。本方法的空间复杂度为$O(logn)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.val = []
    def Insert(self, num):
        if len(self.val) == 0:
            self.val.append(num)
        else:
            i = 0
            while(i<len(self.val)):
                if num <= self.val[i]:
                    break
                i = i+1
            self.val.insert(i,num)
    def GetMedian(self):
        # write code here
        n = len(self.val)
        if n % 2 == 1:
            return self.val[n//2]
        else:
            return (self.val[n//2]+self.val[n//2-1])/2.0