You are viewing a single comment's thread. Return to all comments →
Here is my implementation using 2 heaps in Java. All testcases passed.
private static DecimalFormat df2 = new DecimalFormat(".#"); private static PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); private static PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); static double[] runningMedian(int[] a) { /* * Write your code here. */ if(a == null || a.length == 0) return new double[]{}; List<Double> res = new ArrayList<>(); for(int n : a) { addNum(n); res.add(findMedian()); //System.out.println(res); } double[] val = new double[res.size()]; val = res.stream().mapToDouble(i->i).toArray(); return val; } public static void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if(maxHeap.size() < minHeap.size()) maxHeap.offer(minHeap.poll()); } public static double findMedian() { if(maxHeap.size() == minHeap.size()) return Double.parseDouble(df2.format((maxHeap.peek() + minHeap.peek())/2.0)); else return Double.parseDouble(df2.format(maxHeap.peek() / 1.0)); }
Seems like cookies are disabled on this browser, please enable them to open this website
Find the Running Median
You are viewing a single comment's thread. Return to all comments →
Here is my implementation using 2 heaps in Java. All testcases passed.