java - 优化将数字添加到队列中以获得数字流中的中值

Question

我最近在一次采访中被问到这个问题，目的是从数字数据流中查找中位数，我能够提出优先级队列解决方案，如下所示:

public class MedianFinder {
  private final PriorityQueue<Long> min = new PriorityQueue<>();
  private final PriorityQueue<Long> max = new PriorityQueue<>(Collections.reverseOrder());

  public void addNum(long num) {
    max.offer(num);
    min.offer(max.poll());
    if (max.size() < min.size()) {
      max.offer(min.poll());
    }
  }

  public double findMedian() {
    if (max.size() == min.size())
      return (max.peek() + min.peek()) / 2.0;
    else
      return max.peek();
  }
}

现在面试官希望我优化 addNum 方法，因为它有很多 O(log n) 操作(大约 5)，他想看看我们是否可以进一步优化它，以便我们有更少的O(log n) 次操作？我们可以在这里做些什么来优化 addNum 方法吗？

Answer 1

这可以将 offer 调用的平均次数从 2.5 次减少到 1.5 次，将 poll 调用次数从 1.5 次减少到 0.5 次。总体上将平均 O(log n) 操作数从 4 减少到 2。

public void addNum(long num) {
    if(!max.isEmpty() )
    {
        if(max.size() == min.size())
        {
            if(num > max.peek())
            {
                min.offer(num);
                max.offer(min.poll());
            }
            else
            {
                max.offer(num);
            }
        }
        else
        {
            if(num > max.peek())
            {
                min.offer(num);
            }
            else
            {
                max.offer(num);
                min.offer(max.poll());
            }
        }
    }
    else
    {
        max.offer(num);
    }
}

更紧凑的版本(相同的逻辑)

public void addNum(long num) {
    if(!max.isEmpty())
    {
        (num > max.peek() ? min : max).offer(num);
        if(min.size() > max.size())
        {
            max.offer(min.poll());
        }
        else if(max.size() - min.size() > 1)
        {
            min.offer(max.poll());
        }
    }
    else
    {
        max.offer(num);
    }
}