【重点】【堆】剑指offer——面试题64：数据流中的中位数

力扣

Python

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.left = []  # 大根堆
        self.right = [] # 小根堆
        
    def addNum(self, num: int) -> None:
        if len(self.left) == len(self.right):
            heapq.heappush(self.left, -heapq.heappushpop(self.right, num))
        else:
            heapq.heappush(self.right, -heapq.heappushpop(self.left, -num))

    def findMedian(self) -> float:
        if len(self.left) == len(self.right):
            return (self.right[0] - self.left[0]) / 2
        else:
            return -self.left[0]

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

参考java系列关于堆的梳理。

class MedianFinder {
    PriorityQueue<Integer> queue1; 
    PriorityQueue<Integer> queue2;
    /** initialize your data structure here. */
    public MedianFinder() {
        queue1 = new PriorityQueue<Integer>();
        queue2 = new PriorityQueue<Integer>((a, b) -> b - a); 
    }
    
    public void addNum(int num) {
        if (queue1.size() == queue2.size()) {
            queue2.offer(num);
            queue1.offer(queue2.poll());
        } else {
            queue1.offer(num);
            queue2.offer(queue1.poll());
        }
    }
    
    public double findMedian() {
        return queue1.size() == queue2.size() ? (queue1.peek() + queue2.peek()) / 2.0 : queue1.peek();
    }
}

##Solution1:
最笨的方法了。。。

class Solution {
public:
    void Insert(int num) {
        num_stream.push_back(num);
    }

    double GetMedian() {
        sort(num_stream.begin(),num_stream.end());
        int n = num_stream.size();
        if(n%2 == 1)
            return (double)num_stream[n/2];
        else 
            return (double)(num_stream[n/2] + num_stream[n/2- 1])/2;
    }
private:
    vector<int> num_stream;
};

##Solution2:
利用最大堆和最小堆实现。
注意在C++的priority_queue中默认的less比较是最大值优先级别最高，top()返回最大值；greater是最小值优先级别最高，top()返回最小值。

class Solution {
    priority_queue<int, vector<int>, less<int> > p;
    priority_queue<int, vector<int>, greater<int> > q;
public:
    void Insert(int num) {
        if (p.empty() || num <= p.top()) p.push(num);
        else 
            q.push(num);
        if (p.size() == q.size() + 2) 
            q.push(p.top()), p.pop();
        if (p.size() + 1 == q.size()) 
            p.push(q.top()), q.pop();
    }
    double GetMedian(){ 
      return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();
    }
};