Leetcode 295.数据流的中位数

Posted on |

295.数据流的中位数

题目

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
例如，

[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 范围内，你将如何优化你的算法？

方法

方法1：两个堆

采用两个堆，左半部分smaller是最大堆，右半部分larger是最小堆，每个堆都包含数组一半的元素。
smaller的长度总是保持n/2，larger的长度是n/2或n/2+1，这取决于n的奇偶性。

在添加新元素之前，有两种情况（一共有n个元素，k=n/2）

1
2
(1) length of (small, large) == (k, k)
(2) length of (small, large) == (k, k + 1)

添加新元素后，一共包含n+1个元素

1
2
(1) length of (small, large) == (k, k + 1)
(2) length of (small, large) == (k + 1, k + 1)

第一种情况，larger会多一个元素，smaller会长度保持不变，但是不能直接将新元素添加到larger。应该将新元素push到smaller，再pop出最大元素，并将其push到larger

第二种情况，smaller会多一个元素，larger会长度保持不变，但不能直接将新元素添加到smaller。应该将新元素push到larger，再pop出最小元素，并将其push到smaller。

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
35
from heapq import *
class MedianFinder(object):

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


    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        if len(self.small)==len(self.large):
            heappush(self.large, -heappushpop(self.small,-num))
        else:
            heappush(self.small, -heappushpop(self.large,num))


    def findMedian(self):
        """
        :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:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
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
35
36
37
38
39
40
41
42
from heapq import heappush,heappop
class MedianFinder(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min_heap=[2**32-1]
        self.max_heap=[2**32-1]  
        self.size=0
    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        if (self.size&1)==0:
            if num<=-self.max_heap[0]:
                heappush(self.min_heap,-heappop(self.max_heap))
                heappush(self.max_heap,-num)
            else:
                heappush(self.min_heap,num)
        else:
            if num>=self.min_heap[0]:
                heappush(self.max_heap,-heappop(self.min_heap))
                heappush(self.min_heap,num)
            else:
                heappush(self.max_heap,-num)
        self.size+=1

    def findMedian(self):
        """
        :rtype: float
        """
        if self.size&1:
            return self.min_heap[0]
        return (self.min_heap[0]-self.max_heap[0])/2.


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

方法2

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
class MedianFinder(object):

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


    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """

        bisect.insort(self.l,num)

    def findMedian(self):
        """
        :rtype: float
        """
        b = (len(self.l)-1)/2
        e = len(self.l)/2
        return (self.l[b]+self.l[e])*1.0/2


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