算法1：二分

from bisect import bisect
class Solution:
    def __init__(self):
        self.nums = []

    def insert(self, num):
        """
        :type num: int
        :rtype: void
        """
        self.nums.insert(bisect(self.nums, num), num)

    def getMedian(self):
        """
        :rtype: float
        """
        m = len(self.nums) // 2
        return (self.nums[m] + self.nums[m - 1]) / 2 if len(self.nums) % 2 == 0 else self.nums[m]

算法2：双堆

import heapq
class Solution:
    def __init__(self):
        self.miheap = []
        self.mxheap = []
    def insert(self, num):
        """
        :type num: int
        :rtype: void
        """
        if not self.miheap and not self.mxheap:
            heapq.heappush(self.mxheap, -num)
        elif len(self.miheap) > len(self.mxheap):
            if self.miheap[0] <= num:
                heapq.heappush(self.mxheap, -heapq.heappop(self.miheap))
                heapq.heappush(self.miheap, num)
            else:
                heapq.heappush(self.mxheap, -num)
        elif len(self.miheap) < len(self.mxheap):
            if -self.mxheap[0] >= num:
                heapq.heappush(self.miheap, -heapq.heappop(self.mxheap))
                heapq.heappush(self.mxheap, -num)
            else:
                heapq.heappush(self.miheap, num)
        else:
            if num < self.miheap[0]:
                heapq.heappush(self.mxheap, -num)
            else:
                heapq.heappush(self.miheap, num)
    def getMedian(self):
        """
        :rtype: float
        """
        if len(self.miheap) > len(self.mxheap):
            return self.miheap[0]
        elif len(self.mxheap) > len(self.miheap):
            return -self.mxheap[0]
        else:
            return (-self.mxheap[0] + self.miheap[0]) / 2