leetcode: MedianFinder: passed

unrealwork · unrealwork · commit 168e4acc2eab · 2022-11-12T06:34:03.000+04:00
diff --git a/src/main/java/com/leetcode/twoheaps/MedianFinder.java b/src/main/java/com/leetcode/twoheaps/MedianFinder.java
@@ -0,0 +1,68 @@
+package com.leetcode.twoheaps;
+
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+public final class MedianFinder {
+
+
+    private static final int TWO = 2;
+    private final PriorityQueue<Integer> maxHeap;
+    private final PriorityQueue<Integer> minHeap;
+    private Double median;
+
+    public MedianFinder() {
+        this.maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
+        this.minHeap = new PriorityQueue<>();
+    }
+
+    public void addNum(int num) {
+        if (maxHeap.isEmpty()) {
+            maxHeap.add(num);
+        } else {
+            final int size = size();
+            if (size % TWO == 0) {
+                if (num < minHeap.peek()) {
+                    maxHeap.add(num);
+                } else {
+                    maxHeap.add(minHeap.remove());
+                    minHeap.add(num);
+                }
+            } else {
+                if (num < maxHeap.peek()) {
+                    minHeap.add(maxHeap.remove());
+                    maxHeap.add(num);
+                } else {
+                    minHeap.add(num);
+                }
+            }
+        }
+        median = null;
+    }
+
+    public double findMedian() {
+        if (median == null) {
+            median = calcMedian();
+        }
+        return median;
+    }
+
+    private double calcMedian() {
+        int size = size();
+        if (size % TWO == 0) {
+            if (minHeap.isEmpty() || maxHeap.isEmpty()) {
+                throw new IllegalStateException();
+            }
+            return (minHeap.peek().doubleValue() + maxHeap.peek()) / TWO;
+        } else {
+            if (maxHeap.isEmpty()) {
+                throw new IllegalStateException();
+            }
+            return maxHeap.peek().doubleValue();
+        }
+    }
+
+    private int size() {
+        return minHeap.size() + maxHeap.size();
+    }
+}
diff --git a/src/test/java/com/leetcode/twoheaps/MedianFinderTest.java b/src/test/java/com/leetcode/twoheaps/MedianFinderTest.java
@@ -0,0 +1,27 @@
+package com.leetcode.twoheaps;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+class MedianFinderTest {
+
+    public static final double EPS = 10e-6;
+
+    @Test
+    @DisplayName("Testing MedianFinder API")
+    void test() {
+        final MedianFinder finder = new MedianFinder();
+        finder.addNum(1);
+        assertEquals(1, finder.findMedian(), EPS);
+        finder.addNum(2);
+        assertEquals(1.5, finder.findMedian(), EPS);
+        finder.addNum(3);
+        assertEquals(2, finder.findMedian(), EPS);
+        finder.addNum(-1);
+        assertEquals(1.5, finder.findMedian(), EPS);
+        finder.addNum(-3);
+        assertEquals(1, finder.findMedian(), EPS);
+    }
+}
