295. 数据流的中位数 [hard]

https://leetcode-cn.com/problems/find-median-from-data-stream/

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

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

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

进阶:

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

通过次数22,701 | 提交次数46,997

Third Try

2020-09-20

参考题解才直到的最大最小堆解法，没想到在两个堆之间不停挪移数据，其实是能够实现两个堆的数量相等(或者相差1)，并且较大的数值都在极小堆，较小的数值都在极大堆。很巧妙的，两个堆顶就都是中位数。

相比于二分法插入，其实就是在插入数据的时候仍然为O(lgN)的复杂度。

看评论取中位数用两个堆已经是默认解法了，没遇到过还真是吃亏。

对数据分为两部分，并分别放在最小堆和最大堆中。

比较小的数据，都放在最大堆中

比较大的数据，都放在最小堆中。

维持最大堆的数据比最小堆的数据数量多(其实反过来也行)，并最多大1个，这1个就是在奇数的情况下的中位数。

如果两个堆的数量一样多，则两个堆顶的平均值就是中位数。

重点是数据的插入。

首先先放到最大堆中，由于这时候最小堆会不平衡，于是从最大堆中拿出最大值放到最小堆中。

如果放到最小堆后，数据比最大堆大，则拿出最小值放回最大堆中。
这样就能维持两个堆的数据平衡。

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        
        对数据分为两部分，并分别放在最小堆和最大堆中
        比较小的数据，都放在最大堆中
        比较大的数据，都放在最小堆中
        维持最大堆的数据比最小堆的数据数量多(其实反过来也行)，并最多大1个，这1个就是在奇数的情况下的中位数。
        如果两个堆的数量一样多，则两个堆顶的平均值就是中位数。

        重点是数据的插入。
        首先先放到最大堆中，由于这时候最小堆会不平衡，于是从最大堆中拿出最大值放到最小堆中。
        如果放到最小堆后，数据比最大堆大，则拿出最小值放回最大堆中。
        这样就能维持两个堆的数据平衡。
        """
        self.heap_min = []
        self.heap_max = []  # max堆存负值

    def addNum(self, num: int) -> None:
        heapq.heappush(self.heap_max, - num)
        heapq.heappush(self.heap_min, - heapq.heappop(self.heap_max))
        if len(self.heap_min) > len(self.heap_max):
            heapq.heappush(self.heap_max, - heapq.heappop(self.heap_min))

    def findMedian(self) -> float:
        if len(self.heap_max) > len(self.heap_min):
            return - self.heap_max[0]
        return (-self.heap_max[0] + self.heap_min[0]) / 2.0 

执行用时：244 ms, 在所有 Python3 提交中击败了64.96%的用户
内存消耗：24.7 MB, 在所有 Python3 提交中击败了14.36%的用户

Second Try

2020-09-20

维持一个有序数组，每次插入的时候使用二分法找到插入点。

插入点index的右边都比该点大，左边可以小于等于该点, 就是二分法bisect中的insert_right。

二分法找定位点是O(lgN)的复杂度，但是在列表里插入一个元素复杂度就是O(N)了。

In [12]: bisect.insort_right?
Docstring:
insort_right(a, x[, lo[, hi]])

Insert item x in list a, and keep it sorted assuming a is sorted.

If x is already in a, insert it to the right of the rightmost x.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
Type:      builtin_function_or_method

class MedianFinder:

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

    def addNum(self, num: int) -> None:
        # self.arr.append(num) 
        # 维持一个有序数组

        if not len(self.arr):
            self.arr.append(num)
            return

        if  num < self.arr[0]:
            self.arr = [num] + self.arr
            return

        if  num > self.arr[-1]:
            self.arr.append(num)
            return 

        lft, rt = 0, len(self.arr) - 1
        while lft <= rt:
            mid = (lft + rt) // 2
            if self.arr[mid] == num:
                lft = mid + 1 # 找到的target为lft,并且arr[lft] > num 
            elif self.arr[mid] < num:
                lft = mid + 1
            elif self.arr[mid] > num:
                rt = mid - 1
        self.arr.insert(lft, num)

    def findMedian(self) -> float:
        rt, res = divmod(len(self.arr), 2)
        lft = rt if res else rt - 1
        return (self.arr[lft] + self.arr[rt]) / 2.0 

执行用时：380 ms, 在所有 Python3 提交中击败了26.21%的用户
内存消耗：24.4 MB, 在所有 Python3 提交中击败了44.33%的用户

First Try

2020-09-20

暴力法竟然也能通过，所以不管三七二十一先用暴力法来一波再来考虑改进。

class MedianFinder:

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

    def addNum(self, num: int) -> None:
        self.arr.append(num)  

    def findMedian(self) -> float:
        self.arr = sorted(self.arr)
        rt, res = divmod(len(self.arr), 2)
        lft = rt if res else rt - 1
        return (self.arr[lft] + self.arr[rt]) / 2.0 


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

执行用时：2004 ms, 在所有 Python3 提交中击败了5.03%的用户
内存消耗：24.3 MB, 在所有 Python3 提交中击败了57.09%的用户

295. 数据流的中位数 [hard]​

Third Try​

Second Try​

First Try​

295. 数据流的中位数 [hard]

Third Try

Second Try

First Try