-
Notifications
You must be signed in to change notification settings - Fork 0
/
Find the Running Median.java
43 lines (37 loc) · 1.56 KB
/
Find the Running Median.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static List<Double> runningMedian(List<Integer> a) {
List<Double> medians = new ArrayList<>();
// Max heap for the lower half of the elements
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Min heap for the upper half of the elements
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : a) {
addNumber(num, maxHeap, minHeap);
rebalanceHeaps(maxHeap, minHeap);
double median = calculateMedian(maxHeap, minHeap);
medians.add(median);
}
return medians;
}
private static void addNumber(int num, PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
}
private static void rebalanceHeaps(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
while (Math.abs(maxHeap.size() - minHeap.size()) > 1) {
if (maxHeap.size() > minHeap.size()) {
minHeap.add(maxHeap.poll());
} else {
maxHeap.add(minHeap.poll());
}
}
}
private static double calculateMedian(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
}
}