python3 数据流中的中位数(两个列表实现)

思路:将数据流拦腰截断，分成前半部分，后半部分，前半部分升序排序，后半部分降序排序，因为待会用列表的pop()时间复杂度为O(1),如果后半部分不降序排序，pop(0)的时间复杂度为O(n)。

两种情况，奇数偶数:

奇数的情况下，如果前半部分空，则直接添加到后半部分，否则，判断num是否大于前半部分的最大值，如果大于，则直接添加到后半部分，后半部分再进行排序，为什么要进行排序？因为你不知道num在后半部分什么位置；如果小于，则将前半部分的尾巴即前半部分最大值pop出来添加到后半部分，排序，然后再将num添加到前半部分，排序。

偶数的情况下，如果num小于后半部分的最小值，则将num添加到前半部分，排序。反之，pop右半部分的最小值给前半部分，排序；将num添加到右半部分，排序。

输出：奇数直接输出右半部分的最小值

偶数值输出(前半部分最大值+后半部分最小值)/ 2.0 记住是2.0，这是python2，除以2的话会直接给你返回整数，这就是有些人在pycharm明明能运行，到了牛客却不行的原因。

class Solution:
    def __init__(self):
        self.count = 0
        self.small = []
        self.big = []

    def Insert(self, num):
        # write code here
        self.count += 1
        if self.count % 2:
            if self.small:
                if num < self.small[-1]:
                    self.big.append(self.small.pop())
                    self.big.sort(reverse=True)
                    self.small.append(num)
                    self.small.sort()
                else:
                    self.big.append(num)
                    self.big.sort(reverse=True)
            else:
                self.big.append(num)
                self.big.sort(reverse=True)
        else:
            if num > self.big[-1]:
                self.small.append(self.big.pop())
                self.small.sort()
                self.big.append(num)
                self.big.sort(reverse=True)


    def GetMedian(self, data):
        # write code here
        if self.count % 2:
            return self.big[-1]
        return (self.big[-1] + self.small[-1]) / 2.0