Untitled
unknown
plain_text
2 years ago
1.8 kB
6
Indexable
public class Solution { public ArrayList<Integer> solve(ArrayList<Integer> A) { ArrayList<Integer> ans= new ArrayList<Integer> (); Medianfinder mf= new Medianfinder(); for(int i=0;i<A.size();i++){ mf.add(A.get(i)); ans.add((int)mf.findMedian()); } return ans; } class Medianfinder{ PriorityQueue<Integer> minHeap= new PriorityQueue<>(); PriorityQueue<Integer> maxHeap=new PriorityQueue<>(Collections.reverseOrder()); public void add (int val){ //insert into minheap insert(minHeap,val); // System.out.print(" (1-minHeap "+minHeap+") maxheap "+maxHeap+") "); if(minHeap.size()>maxHeap.size()){ int min=minHeap.remove(); insert(maxHeap,min); // System.out.print(" 2-adding to maxhead "+maxHeap); } //System.out.print(" (minHeap size"+minHeap.size()+") maxheap.size"+maxHeap.size()+") "); if(maxHeap.size()>minHeap.size()){ int max=maxHeap.remove(); minHeap.add(max); // System.out.print(" 3-Reba to minHeap "+minHeap); //insert(minHeap,max); } } public double findMedian(){ //System.out.print(" (minHeap "+minHeap+") maxheap "+maxHeap+") "); if(minHeap.size()==maxHeap.size()) { return maxHeap.peek(); // CHANGE MADE } //System.out.print(" 4-different heap "); return minHeap.peek(); } } void insert(PriorityQueue heap,int val){ heap.add(val); } }
Editor is loading...