295. Find Median from Data Stream

class MedianFinder {
    public List<Integer> nums;

    /** initialize your data structure here. */
    public MedianFinder() {
        nums = new ArrayList<Integer>();
    }
    
    public void addNum(int num) {
        nums.add(num);
    }
    
    public double findMedian() {
        Collections.sort(nums);
        if (nums.size() % 2 == 1) {
            return (double) nums.get(nums.size() / 2);
        } else {
            double med = nums.get(nums.size() / 2 - 1) + nums.get(nums.size() / 2);
            return med / 2.0;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

Time Limit Exceeded
17/18 test cases passed.
ううう

class MedianFinder {

    private Queue<Long> small = new PriorityQueue(),
                        large = new PriorityQueue();

    public void addNum(int num) {
        large.add((long) num);
        small.add(-large.poll());
        if (large.size() < small.size())
            large.add(-small.poll());
    }

    public double findMedian() {
        return large.size() > small.size()
               ? large.peek()
               : (large.peek() - small.peek()) / 2.0;
    }
}

Runtime: 114 ms, faster than 13.76% of Java online submissions for Find Median from Data Stream.
Memory Usage: 69.7 MB, less than 6.61% of Java online submissions for Find Median from Data Stream.
Heapの使用
デフォルトのキューはmaxHeapです!
中央値を一番上に配置し、数が間違っている場合はポーリングして移動します.
最後のカウントで戻る