@@ -0,0 +1,2283 @@
+/*%0AFind Median from Data Stream My Submissions QuestionEditorial Solution%0ATotal Accepted: 17140 Total Submissions: 77162 Difficulty: Hard%0AMedian is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.%0A%0AExamples: %0A%5B2,3,4%5D , the median is 3%0A%0A%5B2,3%5D, the median is (2 + 3) / 2 = 2.5%0A%0ADesign a data structure that supports the following two operations:%0A%0Avoid addNum(int num) - Add a integer number from the data stream to the data structure.%0Adouble findMedian() - Return the median of all elements so far.%0AFor example:%0A%0Aadd(1)%0Aadd(2)%0AfindMedian() -%3E 1.5%0Aadd(3) %0AfindMedian() -%3E 2%0ACredits:%0ASpecial thanks to @Louis1992 for adding this problem and creating all test cases.%0A%0AHide Company Tags Google%0AHide Tags Heap Design%0A*/%0Aclass MedianFinder %7B%0A%0A    public PriorityQueue%3CInteger%3E maxQ = new PriorityQueue%3CInteger%3E(11,Collections.reverseOrder());%0A    public PriorityQueue%3CInteger%3E minQ = new PriorityQueue%3CInteger%3E();%0A    // Adds a number into the data structure.%0A    public void addNum(int num) %7B//2%0A%0A        if(maxQ.size()==minQ.size())%7B%0A            if(maxQ.size()==0)maxQ.offer(num);//2 ; null%0A            else if(num%3C=minQ.peek())maxQ.offer(num);%0A            else %7BminQ.offer(num);maxQ.offer(minQ.poll());%7D%0A        %7D%0A        else if(maxQ.size()%3CminQ.size())%7B%0A            if(num%3EminQ.peek())%7B%0A                minQ.offer(num);%0A                maxQ.offer(minQ.poll());%0A            %7D%0A            else maxQ.offer(num);%0A        %7D%0A        else%7B// 2; null%0A            if(num%3CmaxQ.peek())%7B%0A                maxQ.offer(num);%0A                minQ.offer(maxQ.poll());%0A            %7D%0A            else minQ.offer(num);//2;3%0A        %7D%0A    %7D%0A%0A    // Returns the median of current data stream%0A    public double findMedian() %7B%0A        //System.out.println(maxQ.size()+%22 %22+minQ.size());%0A        if(maxQ.size()%3EminQ.size())return (double)maxQ.peek();//2%0A        else%7B%0A            if(maxQ.size()==0)return 0;%0A            //System.out.println(%22peek: %22+maxQ.peek()+%22 %22+minQ.peek());%0A            return (double)((maxQ.peek()+minQ.peek())/2.0);%0A        %7D%0A    %7D%0A%7D;%0A%0A// Your MedianFinder object will be instantiated and called as such:%0A// MedianFinder mf = new MedianFinder();%0A// mf.addNum(1);%0A// mf.findMedian();%0A

Create Find_Median_from_Data_Stream.java