@@ -0,0 +1,2037 @@
+import java.util.ArrayList;%0Aimport java.util.Collections;%0Aimport java.util.PriorityQueue;%0Aimport java.util.Queue;%0A%0A/**%0A * Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So%0A * the median is the mean of the two middle values.%0A *%0A * Examples:%0A *%0A * %5B2,3,4%5D , the median is 3%0A *%0A * %5B2,3%5D, the median is (2 + 3) / 2 = 2.5%0A *%0A * Design 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 *%0A * double findMedian() - Return the median of all elements so far.%0A *%0A * For example:%0A *%0A * add(1)%0A *%0A * add(2)%0A *%0A * findMedian() -%3E 1.5%0A *%0A * add(3)%0A *%0A * findMedian() -%3E 2%0A *%0A * Tags: Heap, Design%0A */%0Apublic class FindMedianFromDataStream %7B%0A%0A    static class MedianFinder %7B%0A%0A        // smaller half, max heap%0A        private Queue%3CInteger%3E small = new PriorityQueue%3C%3E(Collections.reverseOrder());%0A        // ;arger half, min heap%0A        private Queue%3CInteger%3E large = new PriorityQueue%3C%3E();%0A%0A        // Adds a number into the data structure.%0A        public void addNum(int num) %7B%0A            small.offer(num);%0A            large.offer(small.poll());%0A            if (small.size() %3C large.size()) %7B%0A                small.offer(large.poll());%0A            %7D%0A        %7D%0A%0A        // Returns the median of current data stream%0A        public double findMedian() %7B%0A            return small.size() == large.size() ? small.peek() + (large.peek() - small.peek()) / 2.0 : small.peek();%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    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        MedianFinder mf = new MedianFinder();%0A        mf.addNum(1);%0A        mf.addNum(2);%0A        // %5B1, 2%5D -%3E %5B1.5%5D%0A        System.out.println(mf.findMedian());%0A        mf.addNum(3);%0A        // %5B1, 2, 3%5D -%3E %5B2%5D%0A        System.out.println(mf.findMedian());%0A    %7D%0A%7D%0A

add 275 Find Median From Data Stream