面试题41：数据流中的中位数 (待理解)

题目：

思路一：
用一个排序好的数组完成操作，插入元素之后进行排序，然后再计算中位数即可，这种方法时间复杂度插入的时间复杂度为O(nlogn)

代码实现一：

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.array = []   #成员变量
    def Insert(self, num):
        # write code here
        self.array.append(num)
        self.array.sort()   #排序
    def GetMedian(self,M):
        # write code here
        length = len(self.array)
        if length % 2 ==1:  #奇数个元素
            return self.array[length/2]
        else:
            return (self.array[length/2] + self.array[length/2-1])/2.0

思路二：
利用最大堆和最小堆来实现，这种思路在leetcode可以通过，牛客网不可以，目前还未消化，待解决！！

代码实现二：

class MedianFinder(object):
    from heapq import *
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.bigHpeap = []
        self.smallHeap = []
    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        if len(self.bigHpeap) == len(self.smallHeap):#总数为偶数时,先插入到大根堆,在插入到小根堆
            heapq.heappush(self.smallHeap, -heapq.heappushpop(self.bigHpeap, -num))
        else:#总数为奇数时,先插入到小根堆,在插入到大根堆
            heapq.heappush(self.bigHpeap, -heapq.heappushpop(self.smallHeap, num))

    def findMedian(self):
        """
        :rtype: float
        """
        if len(self.bigHpeap) == len(self.smallHeap):
            return (-self.bigHpeap[0] + self.smallHeap[0]) / 2.0
        else:
            return self.smallHeap[0]




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

提交结果：

思路一的提交结果 leetcode思路二提交结果