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

数字是随机生成的并传递给一个方法。编写一个程序来查找和维护生成新值的中值。有效地找到随机序列的中值

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

private Comparator<Integer> maxHeapComparator, minHeapComparator; 
private PriorityQueue<Integer> 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 < maxHeap.peek()) { 
     minHeap.offer(maxHeap.poll()); 
     maxHeap.offer(randomNumber); 
    } 
    else { 
     minHeap.offer(randomNumber); 
    } 
    } 
} 

public static double getMedian() { 
    if (maxHeap.isEmpty()) return minHeap.peek(); 
    else if (minHeap.isEmpty()) return maxHeap.peek(); 

    if (maxHeap.size() == minHeap.size()) { 
    return (minHeap.peek() + maxHeap.peek())/2; 
    } else if (maxHeap.size() > 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

谢谢

来源

2011-04-14 q0987

Eww行号。还标记语法突出显示的正确语言。 – Joe 2011-04-14 20:34:17

这功课吗？如果是这样，相应标记。 – Leonel 2011-04-14 20:42:04

“写一个程序..”忘记，这是**你的**作业，而不是我们的。 – 2011-04-14 21:16:49

通过给定的顺序运行它之后，

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

因为最大堆尺寸是>分钟 - 它的中位数返回3。

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

此代码偏向于最大堆的左半部分。

我看不清这个原因为何不正确。

来源

2011-04-14 20:49:44 Srikanth

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

回答

相关问题