package leetcode;

import java.util.TreeSet;

/**
 * https://leetcode.com/problems/find-median-from-data-stream/
 */
public class Problem295 {
    static class MedianFinder {
        private final TreeSet<Integer> set = new TreeSet<>((a, b) -> {
            if (a.intValue() <= b.intValue()) {
                return -1;
            } else {
                return 1;
            }
        });

        // Adds a number into the data structure.
        public void addNum(int num) {
            set.add(num);
        }

        // Returns the median of current data stream
        public double findMedian() {
            Integer[] array = set.toArray(new Integer[0]);
            int mid = array.length / 2;
            if (array.length % 2 == 0) {
                int a = array[mid - 1];
                int b = array[mid];
                return (a + b) / 2.0;
            }
            return array[mid];
        }
    }

    public static void main(String[] args) {
        MedianFinder med = new MedianFinder();
        med.addNum(1);
        System.out.println(med.findMedian()); // 1
        med.addNum(2);
        System.out.println(med.findMedian()); // 1.5
        med.addNum(3);
        System.out.println(med.findMedian()); // 2
    }
}

@@ -29,23 +29,29 @@
 va.util.
-TreeSet
+PriorityQueue
 ;%0A%0A/**%0A 
@@ -200,104 +200,108 @@
 nal 
-TreeSet%3CInteger%3E set = new TreeSet%3C%3E((a, b) -%3E %7B%0A            if (a.intValue() %3C= b.intValue()) %7B
+PriorityQueue%3CInteger%3E maxQueue = new PriorityQueue%3C%3E((a, b) -%3E %7B%0A            return b.compareTo(a);
 %0A   
@@ -301,32 +301,36 @@
 a);%0A        
+%7D);%0A
         
 return -1;%0A 
@@ -321,44 +321,88 @@
     
-return -1;%0A            %7D else %7B%0A    
+private final PriorityQueue%3CInteger%3E minQueue = new PriorityQueue%3C%3E((a, b) -%3E %7B%0A
     
@@ -420,24 +420,23 @@
 urn 
-1;%0A            %7D
+a.compareTo(b);
 %0A   
@@ -549,123 +549,191 @@
     
-set.add(num);%0A        %7D%0A%0A        // Returns the median of current data stream%0A        public double findMedian() %7B%0A
+Integer max = maxQueue.peek();%0A            Integer min = minQueue.peek();%0A            if (minQueue.size() == maxQueue.size()) %7B%0A                if (max != null && num %3C max) %7B%0A       
     
@@ -744,250 +744,293 @@
     
+ 
 Integer
-%5B%5D array = set.toArray(new Integer%5B0%5D);%0A            int mid = array.length / 2;%0A            if (array.length %25 2 == 0) %7B%0A                int a = array%5Bmid - 1%5D;%0A                int b = array%5Bmid%5D;%0A                return (a + b) / 2.0;%0A
+ a = maxQueue.poll();%0A                    minQueue.add(a);%0A                    maxQueue.add(num);%0A                %7D else %7B%0A                    minQueue.add(num);%0A                %7D%0A            %7D else %7B%0A                if (num %3C= min) %7B%0A                    maxQueue.add(num);%0A   
     
@@ -1029,33 +1029,41 @@
 %0A               
-%7D
+ %7D else %7B
 %0A            ret
@@ -1063,25 +1063,43 @@
     
-return array%5Bmid%5D
+        Integer a = minQueue.poll()
 ;%0A  
@@ -1108,163 +1108,194 @@
     
-%7D%0A
+ 
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        MedianFinder med = new MedianFinder();%0A        med.addNum(1);%0A        System.out.println(med.
+   maxQueue.add(a);%0A                    minQueue.add(num);%0A                %7D%0A            %7D%0A        %7D%0A%0A        // Returns the median of current data stream%0A        public double 
 find
@@ -1302,23 +1302,18 @@
 Median()
-); // 1
+ %7B
 %0A       
@@ -1317,149 +1317,241 @@
     
-med.addNum(2);%0A        System.out.println(med.findMedian()); // 1.5%0A        med.addNum(3);%0A        System.out.println(med.findMedian()); // 2
+    if (maxQueue.size() == minQueue.size()) %7B%0A                int max = maxQueue.peek();%0A                int min = minQueue.peek();%0A                return (max + min) / 2.0;%0A            %7D%0A            return minQueue.peek();%0A        %7D
 %0A   

Solve problem 295