【LeetCode】剑指 Offer 41. 数据流中的中位数

文章目录

• 【LeetCode】剑指 Offer 41. 数据流中的中位数

package offer;

import java.util.PriorityQueue;
import java.util.Queue;

public class Solution41 {

    public static void main(String[] args) {
        Solution41 solution = new Solution41();
        solution.addNum(1);
        solution.addNum(2);
        System.out.println(solution.findMedian());
        solution.addNum(3);
        System.out.println(solution.findMedian());
    }

    Queue<Integer> A,B;
    public Solution41(){
        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(){
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}