有效地找到随机序列的中值

数字随机生成并传递给方法。 编写程序以在生成新值时查找并维护中值。

堆大小可以相等，或者下面的堆有一个额外的堆。

private Comparator maxHeapComparator, minHeapComparator; private PriorityQueue maxHeap, minHeap; public void addNewNumber(int randomNumber) { if (maxHeap.size() == minHeap.size()) { if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) { maxHeap.offer(minHeap.poll()); minHeap.offer(randomNumber); } else { maxHeap.offer(randomNumber); } } else { // why the following block is correct? // I think it may create unbalanced heap size if(randomNumber  minHeap.size()) { return maxHeap.peek(); } else { return minHeap.peek(); } } 

假设解决方案是正确的，那么我不明白为什么代码块（请参阅我的注释）可以保持堆大小平衡。 换句话说，两个堆的大小差异是0或1。

 Let us see an example, given a sequence 1, 2, 3, 4, 5 The first random number is **1** max-heap: 1 min-heap: The second random number is **2** max-heap: 1 min-heap: 2 The third random number is **3** max-heap: 1 2 min-heap: 3 4 The fourth random number is **4** max-heap: 1 2 3 min-heap: 4 5 

谢谢

Answer 1

在通过给定的序列运行之后，

 max-heap : 1, 2, 3 min-heap : 4, 5 

因为最大堆大小是> min-heap，所以它返回3作为中位数。

max-heap存储左半部分的元素，min-heap存储序列的右半部分。

这段代码偏向左半边是max-heap。

我不明白为什么这段代码不正确。