Given running stream of integers ( or read from dataset ), find out median of the stream you got so far.
To understand this problem better consider stream as 7, 3, 9, 12.
When you have read 7 : Median 7
When you have read 7, 3 : Median 5
When you have read 7, 3, 9 : Median 7
When you have read 7, 3, 9, 12 : Median 8
Approach 1:
You can use two priority queues. First would be Minimum priority Q and second would be maximum priority Q. Goal is to arrange number so that min priority Q would have numbers greater than median and max priority Q would have numbers less than median. Also after entering the numbers in Q we would balance the queues such that both Q should have equal element or one less element than other Q. So that median can be always top element from either of the queue.
Approach 2:
You can implement self balancing tree and put the values in tree such as; values less than median would be put to left of root and values greater than median would be pushed to write of the tree root. With this approach, root would be a median in case of odd number of elements.
import java.util.Collections; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; public class test { public static void main(String args[]) { PriorityQueueminQ = new PriorityQueue (10); PriorityQueue maxQ = new PriorityQueue (10, Collections.reverseOrder()); int i = 0; Scanner sc = new Scanner(System.in); int median = 0; while (i++ < 10) { int val = sc.nextInt(); if(i == 1) { maxQ.add(val); System.out.println("Median : " + val ); median = val; } else{ if ( val > median) minQ.add(val); else maxQ.add(val); int diff = 0; do { diff = Math.abs( maxQ.size() - minQ.size() ); if (diff == 0) { median = (maxQ.peek() + minQ.peek()) / 2; break; } else { if (diff == 1) { if (maxQ.size() > minQ.size()) median = maxQ.peek(); else median = minQ.peek(); break; } else { //If queues is not balanced, balance the queues PriorityQueue high = maxQ.size() > minQ.size() ? maxQ : minQ; PriorityQueue low = maxQ.size() > minQ.size() ? minQ : maxQ; low.add(high.poll()); } } }while (diff > 1); System.out.println("Median : " + median ); } } } }
Comments are welcome.
No comments:
Post a Comment