Numbers keep coming, return the median of numbers at every time a new number added

Clarification
What’s the definition of Median?

  • Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n - 1) / 2]. For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.

Example

  • For numbers coming list: [1, 2, 3, 4, 5], return [1, 1, 2, 2, 3].
  • For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3].
  • For numbers coming list: [2, 20, 100], return [2, 2, 20].

这个题目跟leetcode 295. Find Median from Data Stream 基本一样。
开始没有仔细看题目，当数组长度为偶数的时候要返回中间两个值的较小值，而不是两数的平均数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] medianII(int[] nums) {
    int[] ans = new int[nums.length];
    PriorityQueue<Integer> min = new PriorityQueue<>();
    PriorityQueue<Integer> max = new PriorityQueue<>(10, Collections.reverseOrder());
    for (int i = 0; i < nums.length; i++) {
        int n = nums[i];
        max.offer(n);
        min.offer(max.poll());
        while (min.size() > max.size()) {
            max.offer(min.poll());
        }
        ans[i] = max.peek();
    }
    return ans;
}