@@ -0,0 +1,1900 @@
+/*%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.%0AExamples:%0A%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%0A    void addNum(int num) - Add a integer number from the data stream to the data structure.%0A    double findMedian() - Return the median of all elements so far.%0A%0AFor example:%0A%0Aadd(1)%0Aadd(2)%0AfindMedian() -%3E 1.5%0Aadd(3) %0AfindMedian() -%3E 2%0A%0A*/%0A%0A// note: any class is a set of variables and functions.%0A// search here is search for a string that starts from the root and must end with the root's endpoint%0Aimport java.io.*;%0Aimport java.util.*;%0Apublic class FindMedianfromDataStream %7B%0A%09public static class MedianFinder %7B%0A%09    private Queue%3CLong%3E small = new PriorityQueue(),%0A                        large = new PriorityQueue();%0A    %0A%09    // Adds a number into the data structure.%0A%09%09public void addNum(int num) %7B%0A%09%09%09large.add((long)num);%0A%09        small.add(-large.poll());%0A%09%09    if(large.size() %3C small.size())%7B%0A%09%09%09    large.add(-small.poll());%0A%09        %7D%0A%09    %7D%0A%0A%09    // Returns the median of current data stream%0A%09%09public double findMedian() %7B%0A%09%09%09if(large.size() == small.size())%7B%0A%09%09%09%09return (large.peek() - small.peek())/2.0;%0A%09        %7Delse%7B%0A%09%09        return large.peek();%0A%09        %7D%0A%09    %7D%0A%09%7D;%09%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%0A%09public static void main(String%5B%5D args) %7B %0A%09%09MedianFinder mf = new MedianFinder();%0A%09%09Scanner reader = new Scanner(System.in);  // Reading from System.in%0A%09%09System.out.println(%22Add a number: %22);%0A%09%09while(reader.hasNextInt())%7B%0A%09%09%09int n = reader.nextInt();%0A%09%09%09mf.addNum(n);%0A%09%09%09System.out.println(%22Median number:%22 + mf.findMedian());%0A%09%09%7D%0A%09%09return;%0A%09%7D%09%0A%7D%0A

use priority queue, simple