I'm trying to solve a challenge where you need to calculate the median every time you add a number.
say you have a list of numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
When you scan in the first number (1), you calculate the median of that. When you scan in the second number (2), you calculate the median of 1 and 2, and so on.
My code is working, but is having timeout issues on the larger test cases:
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
PriorityQueue<Integer> pq = new PriorityQueue<>();
while(n-- > 0) {
pq.add(s.nextInt());
System.out.println(calculateMedian(pq));
}
}
public static float calculateMedian(PriorityQueue<Integer> pq) {
PriorityQueue<Integer> temp = new PriorityQueue<>(pq);
int index = 0;
float number = 0.0f;
int halfQueueSize = (temp.size() >> 1);
if(temp.size() % 2 != 0) {
while(index++ <= halfQueueSize) {
number = temp.poll();
}
return number;
} else {
while(index++ < halfQueueSize) {
number = temp.poll();
}
return ((number+temp.poll())/2.0f);
}
}
}
Any tips as to how this can be optimized would be much appreciated!
TreeMap
w.r.t. the complexity, but practically it should be way faster. \$\endgroup\$