update 295

fishercoder1534 · fishercoder1534 · commit 910ca97a641f · 2024-01-26T15:54:58.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_295.java b/src/main/java/com/fishercoder/solutions/_295.java
@@ -48,8 +48,8 @@ public static class Solution2 {
         public static class MedianFinder {
             /**
              * credit: https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1
-             * The idea is for sure to use two heaps, one is max heap, one is min heap, we always let the max heap be one element
-             * bigger than min heap if the total number of elements is not even.
+             * The idea is for sure to use two heaps, one is max heap, one is min heap, we always let the max heap have one more element
+             * than min heap if the total number of elements is not even.
              * we could always get the median in O(1) time.
              * 1. use Long type to avoid overflow
              * 2. negate the numbers for small heap to save the effort for writing a reverse comparator, brilliant!
@@ -85,4 +85,41 @@ public double findMedian() {
 
         }
     }
+
+    public static class Solution3 {
+        public static class MedianFinder {
+            /**
+             * The same as Solution2, but not using negation for minHeap.
+             */
+
+            private Queue<Long> maxHeap;
+            private Queue<Long> minHeap;
+
+            /**
+             * initialize your data structure here.
+             */
+            public MedianFinder() {
+                maxHeap = new PriorityQueue<>();
+                minHeap = new PriorityQueue<>((a, b) -> (int) (b - a));
+            }
+
+            // Adds a number into the data structure.
+            public void addNum(int num) {
+                maxHeap.offer((long) num);
+                minHeap.offer(maxHeap.poll());
+                if (maxHeap.size() < minHeap.size()) {
+                    maxHeap.offer(minHeap.poll());
+                }
+            }
+
+            // Returns the median of current data stream
+            public double findMedian() {
+                if (maxHeap.size() > minHeap.size()) {
+                    return maxHeap.peek();
+                }
+                return (maxHeap.peek() + minHeap.peek()) / 2.0;
+            }
+
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_295Test.java b/src/test/java/com/fishercoder/_295Test.java
@@ -1,20 +1,22 @@
 package com.fishercoder;
 
 import com.fishercoder.solutions._295;
-import org.junit.BeforeClass;
-import org.junit.Test;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
 
-import static org.junit.Assert.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertEquals;
 
 /**
  * Created by fishercoder on 5/27/17.
  */
 public class _295Test {
     private static _295.Solution1.MedianFinder solution1;
+    private static _295.Solution2.MedianFinder solution2;
 
-    @BeforeClass
-    public static void setup() {
+    @BeforeEach
+    public void setup() {
         solution1 = new _295.Solution1.MedianFinder();
+        solution2 = new _295.Solution2.MedianFinder();
     }
 
     @Test
@@ -24,4 +26,12 @@ public void test1() {
         solution1.addNum(-1);
         assertEquals(1.0, solution1.findMedian(), 0);
     }
+
+    @Test
+    public void test2() {
+        solution2.addNum(1);
+        solution2.addNum(3);
+        solution2.addNum(-1);
+        assertEquals(1.0, solution2.findMedian(), 0);
+    }
 }
