703. Kth Largest Element in a Stream
Easy
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.
"""
1 import heapq
2 def heapsort(iterable):
3 h = []
4 for i in iterable:
5 heapq.heappush(h, i)
6 return [heapq.heappop(h) for i in range(len(h))]
7
8 # method 1: sort to list
9 s = [3, 5, 1, 2, 4, 6, 0, 1]
10 print(heapsort(s))
11 '''
12 [0, 1, 1, 2, 3, 4, 5, 6]
13 '''
"""
import heapq
class KthLargest(object):
def __init__(self, k, nums):
"""
:type k: int
:type nums: List[int]
"""
self.arr = []
self.k = k
for i in nums:
if len(self.arr) < self.k:
heapq.heappush(self.arr, i)
else:
if i > self.arr[0]:
#if heapq.nsmallest(1, self.arr)[0] < i:
heapq.heapreplace(self.arr, i)
#heapq.heappop(self.arr)
#heapq.heappush(self.arr, i)
def add(self, val):
"""
:type val: int
:rtype: int
"""
if len(self.arr) < self.k:
heapq.heappush(self.arr, val)
else:
if val > self.arr[0]:
#if heapq.nsmallest(1, self.arr)[0] < val:
heapq.heapreplace(self.arr, val)
#heapq.heappop(self.arr)
#heapq.heappush(self.arr, val)
assert len(self.arr) == self.k
return self.arr[0]
#return heapq.nsmallest(1, self.arr)[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
注意:如果使用heapq.nsmallest(1, self.arr)[0]来返回heap的最小值会有超时问题。
标签:heapq,val,Stream,self,KthLargest,arr,Element,add From: https://blog.51cto.com/u_11908275/6381043