剑指 Offer 41. 数据流中的中位数

class MedianFinder {
    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;
    public MedianFinder() {
        left = new PriorityQueue<Integer>((a, b) -> b - a);
        right = new PriorityQueue<Integer>();
    }
    
    public void addNum(int num) {
        if(left.isEmpty() || num <= left.peek()){ // left 为空或 num <= 中位数（大根堆堆顶元素）
            left.offer(num);  
            if(left.size() - right.size() > 1){ // 转移小堆顶到大堆
                right.offer(left.poll());
            } 
        } else {
            right.offer(num);
            if(right.size() > left.size()) {
                left.offer(right.poll());
            }
        }
    }    
    public double findMedian() {
        return left.size() > right.size() ? left.peek() : (left.peek() + right.peek()) / 2.0;
    }
}
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

class MedianFinder:
    def __init__(self):
        self.q = []

    def addNum(self, num: int) -> None:
        insort_left(self.q, num)

    def findMedian(self) -> float:
        n = len(self.q)
        return (self.q[n // 2] + self.q[(n-1) // 2]) / 2
1
2
3
4
5
6
7
8
9
10

from sortedcontainers import SortedList
class MedianFinder:
    def __init__(self):
        self.sl = SortedList()

    def addNum(self, num: int) -> None:
        self.sl.add(num)      
        
    def findMedian(self) -> float:
        n = len(self.sl)
        return (self.sl[n // 2] + self.sl[(n-1)//2]) / 2
1
2
3
4
5
6
7
8
9
10
11