题目描述

题解

列表（不推荐）

在不考虑时间复杂度仅仅实现功能的情况下, 用一个列表就可以实现题目要求

public class MedianFinder {
    /** initialize your data structure here. */
    List<Integer> list;
    public MedianFinder() {
        this.list = new ArrayList<>();
    }

    public void addNum(int num) {
        list.add(num);
    }

    public double findMedian() {
        Collections.sort(list);
        int len = list.size();
        int mid = len/2;
        if (len==0){
            return list.get(0);
        }else if (len%2==0){
            return (list.get(mid-1)+list.get(mid))/2.0;
        }else {
            return list.get(mid);
        }

    }
}

堆

可以通过辅助堆来实现

这里使用两个堆, 一个大根堆来保存较小的一半数字, 一个小根堆来保存较大的一半数字

因此求中位数是直接在两个堆的堆顶取值即可.

在添加一个数字时, 根据两个堆的元素数量就可以知道当前为奇数还是偶数. 如果堆A的数量大, 则应该往B中添加元素, 不过添加的元素要先加到A里, 然后把堆顶元素弹出再进入B; 同理, 当两个堆数量相同时该往A里添加, 但是要先在B里过一下, 把B的堆顶元素弹出到A中. 非常巧妙的思路

Queue<Integer> A, B;

public MedianFinder() {
    A = new PriorityQueue<>();
    B = new PriorityQueue<>((x, y) -> y - x);
}

public void addNum(int num) {
    if (A.size() != B.size()) {
        A.add(num);
        B.add(A.poll());
    } else {
        B.add(num);
        A.add(B.poll());
    }
}

public double findMedian() {
    if (A.size() != B.size()) {
        return A.peek();
    } else {
        return (A.peek() + B.peek()) / 2.0;
    }

}