数字是随机生成并传递给方法的。编写一个程序,在生成新值时查找并维护中值。
堆大小可以相等,或者下面的堆多出一个。
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
谢谢
最佳答案
按照给定的顺序运行它之后,
max-heap : 1, 2, 3
min-heap : 4, 5
因为最大堆大小 > 最小堆,它返回 3 作为中值。
最大堆大约存储左半部分的元素,最小堆大约存储右半部分的序列。
这段代码偏向左半边,即最大堆。
我不明白为什么这段代码不正确。
关于java - 有效地找到随机序列的中值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5669316/