aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--kth_largest_element_stream.c4
-rw-r--r--kth_largest_element_stream.cpp11
-rw-r--r--kth_largest_element_stream.py46
3 files changed, 54 insertions, 7 deletions
diff --git a/kth_largest_element_stream.c b/kth_largest_element_stream.c
index f7ec953..23c0762 100644
--- a/kth_largest_element_stream.c
+++ b/kth_largest_element_stream.c
@@ -1,7 +1,5 @@
// 703. Kth Largest Element in a Stream
-#include <limits.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
/*
* design a class to find the k'th largest element in a stream. note that it is
diff --git a/kth_largest_element_stream.cpp b/kth_largest_element_stream.cpp
index 805d144..3ef8b3c 100644
--- a/kth_largest_element_stream.cpp
+++ b/kth_largest_element_stream.cpp
@@ -33,8 +33,11 @@ public:
};
int main() {
- int k, val;
- vector<int> nums;
- KthLargest *obj = new KthLargest(k, nums);
- int param_1 = obj->add(val);
+ vector<int> nums = {4, 5, 8, 2};
+ KthLargest *obj = new KthLargest(3, nums);
+ printf("%d\n", obj->add(3)); // expect: 4
+ printf("%d\n", obj->add(5)); // expect: 5
+ printf("%d\n", obj->add(10)); // expect: 5
+ printf("%d\n", obj->add(9)); // expect: 8
+ printf("%d\n", obj->add(4)); // expect: 8
}
diff --git a/kth_largest_element_stream.py b/kth_largest_element_stream.py
new file mode 100644
index 0000000..d92b797
--- /dev/null
+++ b/kth_largest_element_stream.py
@@ -0,0 +1,46 @@
+# 703. Kth Largest Element in a Stream
+import heapq
+
+"""
+design a class to find the k'th largest element in a stream. note that it is
+the k'th largest element in the sorted order, not the k'th distinct element.
+implement 'KthLargest' class:
+- KthLargest(int k, int[] nums) initialises the objct with the integer 'k'
+and the stream of integers 'nums' int add(int val) appends the integer 'val'
+to the stream and returns the element representing the k'th largest stream
+element
+"""
+
+
+class KthLargest(object):
+ def __init__(self, k, nums):
+ """
+ :type k: int
+ :type nums: List[int]
+ """
+ self.pool = nums
+ self.k = k
+ heapq.heapify(self.pool)
+ while len(self.pool) > k:
+ heapq.heappop(self.pool)
+
+ def add(self, val):
+ """
+ :type val: int
+ :rtype: int
+ """
+ if len(self.pool) < self.k:
+ heapq.heappush(self.pool, val)
+ elif val > self.pool[0]:
+ heapq.heapreplace(self.pool, val)
+ return self.pool[0]
+
+
+if __name__ == "__main__":
+ nums = [4, 5, 8, 2]
+ obj = KthLargest(3, nums)
+ print(obj.add(3))
+ print(obj.add(5))
+ print(obj.add(10))
+ print(obj.add(9))
+ print(obj.add(4))