(leetcode 295)数据流的中位数（暴力、二分、小顶堆以及进阶）

原题如下：

1、暴力法

暴力法是把这个问题看成许多分开的求中位数的问题，每次求之前对已有数据排序，然后根据下标求出中位数。
时间复杂度在于排序，为O（nlogn）。
思路和代码都比较简单，不赘述了。

2、二分

采用插入排序的思想，从一开始就维护一个有序列表。
二分法找到新元素对应的位置后插入，求中位数时根据下标直接提取。
二分找位置本身时O(logn)的复杂度，但是插入的时候可能会造成列表后面元素的移动，最坏的时候为O（n）的时间复杂度，因此整体时间复杂度为O（n）。

代码：

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lst=[]

    def addNum(self, num: int) -> None:
        if self.lst==[]:
            self.lst.append(num)
            return
        left,right=0,len(self.lst)-1
        while left<=right:
            mid=(left+right)//2
            if left==mid:
                if self.lst[left]>num:
                    self.lst.insert(left,num)
                elif self.lst[right]>num:
                    self.lst.insert(right,num)
                else:
                    self.lst.insert(right+1,num)
                break
            if self.lst[mid]==num:
                self.lst.insert(mid,num)
                break
            elif self.lst[mid]<num:
                left=mid
            else:
                right=mid
                
    def findMedian(self) -> float:
        #print(self.dic,self.t)
        l=len(self.lst)
        #print(l)
        if l&1:
            return round(self.lst[l//2],1)
        else:
            return round((self.lst[l//2-1]+self.lst[l//2])/2,1)

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

3、利用两个堆

原题解（本思路代码也是这篇题解的）
思路：维护两个堆，一个大顶堆，一个小顶堆，并且“小顶堆长度-大顶堆长度<=1”，方便找中位数。
大顶堆中的元素都较小，使得堆顶上最大的元素也小于小顶堆里最小的元素；
同样，小顶堆中的元素都较大，使得堆顶上最小的元素也大于大顶堆里最啊的元素，举例如图：

这样做的好处是使得每次移动元素时，堆之间只需移动一个元素。
举例说明数据流向：
插入新数字1时，因为我们一般维持小顶堆的元素略多，所以经大顶堆后流入小顶堆；
大顶堆插入1，排出4；小顶堆插入4；两堆之间流动的数字为4。
此时两个堆情形如下：
下次插入时，因为小顶堆数据多于大顶堆，从小顶堆插入，流向大顶堆。流动完成后两堆中元素数目均为4。
。。。。。。
当求中位数时，对两堆顶的元素操作即可：
（1）当总元素个数为奇数，此时小顶堆元素比大顶堆多一个，返回小顶堆堆顶元素；
（2）当总元素个数为偶素，返回（大顶堆顶+小顶堆顶）/2。

注意：因为python中只提供了小顶堆，因此当我们需要大顶堆时需要将元素取相反数，这样存在小顶堆里的元素相反数实际上达到了大顶堆的效果，注意在堆间移动时的取相反数过程。

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        # 初始化大顶堆和小顶堆
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        if len(self.max_heap) == len(self.min_heap):# 先加到大顶堆，再把大堆顶元素加到小顶堆
            heapq.heappush(self.min_heap, -heapq.heappushpop(self.max_heap, -num))
        else:  # 先加到小顶堆，再把小堆顶元素加到大顶堆
            heapq.heappush(self.max_heap, -heapq.heappushpop(self.min_heap, num))

    def findMedian(self) -> float:
        if len(self.min_heap) == len(self.max_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return self.min_heap[0]

4、进阶思考

（1）如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
（2）如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

如果将数字限定在这个范围里面，大量数字情形下，处理的难度在于大量的重复。

1、对于（1）进阶：

此时，我们没有必要使用O（n）的空间来存储然后排序，只需设置一个长为101的数组存储0-100他们各自的个数，然后根据总数的一半从左往右移动即可找到中位数。时间复杂度在于输入，取中位数时复杂度为O（1）。

2、对于（2）进阶

此时相比较于（1），区别是我们不便使用固定长度的数组，强行使用可能会因为个别极端数字造成大量的空间浪费。
这时候，我们使用字典存储每个键以及他们出现的次数，如果键数较少，我们每次取中位数时，可以对键进行排序然后从左往右找n/2个数得到中位数。

class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.dic={}
        self.t=0
    def addNum(self, num: int) -> None:
        self.t+=1
        if num in self.dic:
            self.dic[num]+=1
        else:
            self.dic[num]=1

    def findMedian(self) -> float:
        #print(self.dic,self.t)
        if self.t&1:
            x=self.t//2
            lst=list(self.dic.keys())
            lst.sort()
            index=-1
            while x>=0:
                index+=1
                x-=self.dic[lst[index]]
            return round(lst[index],1)
        else:
            x=self.t//2
            lst=list(self.dic.keys())
            lst.sort()
            index=-1
            while x>0:
                index+=1
                x-=self.dic[lst[index]]
            if x<0:
                return round(lst[index])
            else:
                return round((lst[index]+lst[index+1])/2,1)
                

遗憾的是，这份代码超时了，应该是测试样例重复较少使得排序时间过长，我们同样可以使用两个堆来对键值排序，需要取出时按照堆的特性从小到大取即可，这里笔者只提供介个思路啦~

不过笔者相信这种思路对于大量重复数据有优化时空复杂度的效果，同时对于少量键值的情况直接排序应该也可以接受。