(python version) 剑指 offer 41. 数据流中的中位数

题目描述

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

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

解题思路

• 在 addNum() 函数当中，排序是重点*** => 时间复杂度的优化

  • 有两种 python可用方法
    (1) bisec：阵列二分演算法 (Array bisection algorithm)

    • bisec.insort_left( list, num) => 是在已排序好的 list 当中，找到适合 num 插入的"位置" 并且 “插入” 。并且在返回的是经过排序好的 list 。
    • bisec.bisec_left (list , num) => 是在已排序好的 list 当中找到适合 num 插入的 “位置”。

    (2) heapq：堆积佇列 (heap queue) 演算法

    • heapq.heappop(heap)：从 heap 取出并回传最小的元素，同时保持 heap 性质不变。
    • heapq.heappush(heap, num)：把 num 放进 heap，并保持 heap 性质不变。
    • heapq.heappushpop(heap, num)：将 num 放入 heap ，接着从 heap 取出并回传最小的元素。这个组合函式比呼叫 heappush() 之后呼叫 heappop() 更有效率。

• Python operator: // : 代表的是 x/y 的商数

  • 例如：x = 15, y = 2; x//y = 7 。

Python 代码

# method1: 使用特殊函数
import bisect
class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lists = []

    def addNum(self, num: int) -> None:
        if not self.lists:
            self.lists = [num]
        # 插入之中
        else:
            bisect.insort_left(self.lists, num)
                
    def findMedian(self) -> float:
        if not self.lists:
            return None
        l = len(self.lists)
        if l %2 != 0:
            return self.lists[math.floor(l/2)]
        else:
            return (self.lists[int(l/2)] + self.lists[int((l/2)-1)])/2


# method2: 时间复杂度超时: 主要发生在insert num 时需遍历 list 
class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lists = []

    def addNum(self, num: int) -> None:
        if not self.lists:
            self.lists = [num]
        # 插入尾部
        elif num >= self.lists[-1]:
            self.lists.append(num)
        # 插入头部
        elif num <= self.lists[0]:
            tmp = [num]
            tmp.extend(self.lists)
            self.lists = tmp
        # 插入之中
        else:
            for i in range(len(self.lists)):
                if num < self.lists[i]:
                    tmp = []
                    tmp.extend(self.lists[:i])
                    tmp.extend([num])
                    tmp.extend(self.lists[i:])
                    self.lists = tmp 
                    break            
                
    def findMedian(self) -> float:
        if not self.lists:
            return None
        l = len(self.lists)
        
        if l %2 != 0:
            return self.lists[math.floor(l/2)]
        else:
            return (self.lists[int(l/2)] + self.lists[int((l/2)-1)])/2

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()