-
Notifications
You must be signed in to change notification settings - Fork 0
/
RunningMedian.java
37 lines (33 loc) · 1.14 KB
/
RunningMedian.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
import java.util.*;
/**
* input a1, a2, a3, ..., an , every time we input a number, print the median so far.
*
* @author LBW
*/
public class RunningMedian {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
PriorityQueue<Integer> lower = new PriorityQueue<Integer>(Comparator.reverseOrder());
PriorityQueue<Integer> higher = new PriorityQueue<>();
while (scanner.hasNext()) {
int i = scanner.nextInt();
addElement(i, lower, higher);
reBalance(lower, higher);
System.out.print(lower.peek() + " ");
}
}
public static void addElement(int i, PriorityQueue<Integer> lower, PriorityQueue<Integer> higher) {
if (lower.size() == 0 || i <= lower.peek())
lower.add(i);
else
higher.add(i);
}
public static void reBalance(PriorityQueue<Integer> lower, PriorityQueue<Integer> higher) {
if (lower.size() < higher.size()) {
lower.add(higher.remove());
}
else if (lower.size() > higher.size() + 1) {
higher.add(lower.remove());
}
}
}