有效地找到一个随机序列的中值 [英] Effectively to find the median value of a random sequence
问题描述
数字是随机生成的,并传递给方法。写一个程序用来发现和维持中位值产生新的价值。
Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
堆的大小可以等于或以下堆中有一个额外的。
The heap sizes can be equal or the below heap has one extra.
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();
}
}
假设该解决方案是正确的,那么我不明白为什么code座(见我的意见)可维持堆大小平衡。换句话说,两个堆的大小差异为0或1
Assume the solution is correct, then I don't understand why the code block(see my comments) can maintain the heap size balance. In other words, the size difference of two heaps is 0 or 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
感谢您
推荐答案
通过给定的顺序运行它之后,
After running it through given sequence,
max-heap : 1, 2, 3
min-heap : 4, 5
因为最大堆大小>分堆返回3为中值。
since max-heap size is > min-heap it returns 3 as the median.
最大堆店左半元素约和最小堆店右半序列的约。
max-heap stores left half of elements approximately and min-heap stores right-half of sequence approximately.
这code偏向左一半是最大堆。
this code biased towards left-half that is max-heap.
我不明白为什么这code是不正确。
I don't see why this code is incorrect.
这篇关于有效地找到一个随机序列的中值的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!