class MedianFinder {
// min heap
// java defaul priority queue is min heap
// use min heap to keep large numbers
PriorityQueue<Integer> large = new PriorityQueue<>();
// use max heap to store small numbers
PriorityQueue<Integer> small = new PriorityQueue<>((a,b)->b-a);
/** initialize your data structure here. */
public MedianFinder() {
}
public void addNum(int num) {
// make small.size()>=large.size();
if(small.size()>large.size()){
//method: offer
large.offer(num);
}else{
small.offer(num);
}
if(small.size() >0 && large.size()>0 && small.peek()>large.peek()){
int temp=small.poll();
small.offer(large.poll());
large.offer(temp);
}
}
public double findMedian() {
if(small.size()==large.size()){
// convert to float
return (small.peek()+large.peek())/2.0;
}else{
return small.peek();
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
follow-up question:
Follow up:
If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Answer:
1
-we maintain HashMap -we also maintain total number of elements, so that median is just total-nums/2 th element from sorted array.
-then we go over Map from 1-100 and count element, when we hit total-nums/2 th element , that is our median
2.
add two variable to count the numbers that smaller and larger than 100 respectively.