diff options
-rw-r--r-- | kth_largest_element_stream.c | 4 | ||||
-rw-r--r-- | kth_largest_element_stream.cpp | 11 | ||||
-rw-r--r-- | kth_largest_element_stream.py | 46 |
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)) |