add 703

fishercoder1534 · fishercoder1534 · commit be763ddc4bb0 · 2019-02-15T14:29:54.000-08:00
diff --git a/README.md b/README.md
@@ -123,6 +123,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |706|[Design HashMap](https://leetcode.com/problems/design-hashmap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_706.java) | O(n) | O(n) | |Easy| Design
 |705|[Design HashSet](https://leetcode.com/problems/design-hashset/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_705.java) | O(1) | O(n) | |Easy| Design
 |704|[Binary Search](https://leetcode.com/problems/binary-search/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_704.java) | O(logn) | O(1) | |Easy| Binary Search
+|703|[Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_703.java) | O(logn) | O(n) | |Easy| 
 |701|[Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_701.java) | O(n) | O(h) | |Medium | DFS, recursion
 |700|[Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_700.java) | O(n) | O(h) | |Easy| recusion, dfs
 |699|[Falling Squares](https://leetcode.com/problems/falling-squares/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_699.java) | O(n^2) | O(n) | |Hard | Segment Tree
diff --git a/src/main/java/com/fishercoder/solutions/_703.java b/src/main/java/com/fishercoder/solutions/_703.java
@@ -0,0 +1,58 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.PriorityQueue;
+
+/**
+ * 703. Kth Largest Element in a Stream
+ *
+ * Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
+ * Your KthLargest class will have a constructor which accepts an integer K and an integer array nums,
+ * which contains initial elements from the stream.
+ * For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.
+ *
+ * Example:
+ *
+ * int K = 3;
+ * int[] arr = [4,5,8,2];
+ * KthLargest kthLargest = new KthLargest(3, arr);
+ * kthLargest.add(3);   // returns 4
+ * kthLargest.add(5);   // returns 5
+ * kthLargest.add(10);  // returns 5
+ * kthLargest.add(9);   // returns 8
+ * kthLargest.add(4);   // returns 8
+ * Note:
+ * You may assume that nums' length ≥ K-1 and K ≥ 1.
+ */
+public class _703 {
+  public static class Solution1 {
+    public static class KthLargest {
+      PriorityQueue<Integer> heap;
+      int K;
+      public KthLargest(int k, int[] nums) {
+        heap = new PriorityQueue<>(Collections.reverseOrder());
+        for (int num : nums) {
+          heap.offer(num);
+        }
+        K = k;
+      }
+
+      public int add(int val) {
+        List<Integer> tmp = new ArrayList<>();
+        int result = 0;
+        int tmpK = K;
+        heap.offer(val);
+        while (tmpK-- > 0) {
+          result = heap.poll();
+          tmp.add(result);
+        }
+        for (int num : tmp) {
+          heap.offer(num);
+        }
+        return result;
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_703Test.java b/src/test/java/com/fishercoder/_703Test.java
@@ -0,0 +1,21 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._703;
+import org.junit.Test;
+
+import static junit.framework.Assert.assertEquals;
+
+public class _703Test {
+  private static _703.Solution1.KthLargest solution1;
+  private static int[] A;
+
+  @Test
+  public void test1() {
+    solution1 = new _703.Solution1.KthLargest(3, new int[] {4, 5, 8, 2});
+    assertEquals(4, solution1.add(3));
+    assertEquals(5, solution1.add(5));
+    assertEquals(5, solution1.add(10));
+    assertEquals(8, solution1.add(9));
+    assertEquals(8, solution1.add(4));
+  }
+}
