leetcode-295-Find-Median-from-Data-Stream

发表于   |  

TOREVIEW

描述

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.

For example,

1
2
[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.

Example:

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

Follow up:

  1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
  2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

分析

用最大堆存放较小的二分之一，用最小堆存放较大的二分之一，每次增加元素时，确保最大堆的元素个数大于等于最小堆。

解决方案1（Python）

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
class MedianFinder:

    def __init__(self):
        self.minHeap = list()
        self.maxHeap = list()

    def addNum(self, num: int) -> None:
        minHeap_ = self.minHeap
        maxHeap_ = self.maxHeap
        
        heapq.heappush(maxHeap_, num)
        heapq.heappush(minHeap_, -maxHeap_[0])
        heapq.heappop(maxHeap_)
        
        if len(minHeap_) > len(maxHeap_):
            heapq.heappush(maxHeap_, -minHeap_[0])
            heapq.heappop(minHeap_)
        

    def findMedian(self) -> float:
        minHeap_ = self.minHeap
        maxHeap_ = self.maxHeap
        if len(minHeap_) == len(maxHeap_):
            return (-minHeap_[0] + maxHeap_[0]) / 2
        return maxHeap_[0]


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

解决方案2(C++)

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
class MedianFinder {
private:
    priority_queue<double> maxHeap;
    priority_queue<double, vector<double>, greater<double>> minHeap;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        return maxHeap.size() == minHeap.size() ? (minHeap.top()+maxHeap.top())/2: maxHeap.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

相关问题

题目来源