卖萌的弱渣

I am stupid, I am hungry.

Find Median From Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • void addNum(int num) - Add a integer number from the data stream to the data structure.
  • double findMedian() - Return the median of all elements so far.

For example:

1
2
3
4
5

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

Solution

  • 维护两个最小堆small, large
  • small中存数组比较小的部分的负数
  • large存比较大的部分
(Find-Median-from-Data-Stream.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class MedianFinder:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.small = [] # 数组的比较小的部分， 最小堆 (存储负数) small[0] 的正数其实是small中最大的
        self.large = [] # 数组的比较大的部分, 最小堆 (存储正数)

    def addNum(self, num):
        """
        Adds a num into the data structure.
        :type num: int
        :rtype: void
        """
        if len(self.small) == len(self.large):
            heapq.heappush(self.large, -heapq.heappushpop(self.small,-num))
        else:
            heapq.heappush(self.small, -heapq.heappushpop(self.large,num))

    def findMedian(self):
        """
        Returns the median of current data stream
        :rtype: float
        """
        if len(self.small) == len(self.large):
            return float(self.large[0]-self.small[0])/2.0
        else:
            return float(self.large[0])


# Your MedianFinder object will be instantiated and called as such:
# mf = MedianFinder()
# mf.addNum(1)
# mf.findMedian()