Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.8 kB
3
Indexable
Never
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);
    }
    
    

}