题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

题目分析

使用两个优先队列，一个大顶存储左侧数据，一个小顶存储右侧数据。
插入数据时，根据大小决定插入左侧还是右侧。然后再对两个队列元素的数量做平衡（差距超过2）。
插入数据的时间复杂度是 O(log n)，读取中位数的时间复杂度是 O(1)

Java

private Queue<Integer> left = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
private Queue<Integer> right = new PriorityQueue<>();

public MedianFinder() {

}

public void addNum(int num) {
    if (right.isEmpty()) {
        right.offer(num);
        return;
    }
    if (num > right.peek()) {
        right.offer(num);
        if (right.size() > left.size() + 1) {
            left.offer(right.poll());
        }
    } else {
        left.offer(num);
        if (left.size() > right.size() + 1) {
            right.offer(left.poll());
        }
    }
}

public double findMedian() {
    if (left.size() > right.size()) {
        return (double) left.peek();
    } else if (left.size() < right.size()) {
        return (double) right.peek();
    } else {
        return (left.peek() + right.peek()) / 2.0;
    }
}

Kotlin

private val left = PriorityQueue<Int> { o1, o2 -> Integer.compare(o2, o1) }
private val right = PriorityQueue<Int>()

fun addNum(num: Int) {
    if (left.isEmpty()) {
        left.offer(num)
        return
    }
    if (num < left.peek()) {
        left.offer(num)
        if (left.size > right.size + 1) {
            right.offer(left.poll())
        }
    } else {
        right.offer(num)
        if (right.size > left.size + 1) {
            left.offer(right.poll())
        }
    }
}

fun findMedian(): Double {
    if (left.size > right.size) {
        return left.peek().toDouble()
    } else if (left.size < right.size) {
        return right.peek().toDouble()
    } else {
        return (left.peek() + right.peek()) / 2.0
    }
}