Day74：数据流中的第K大元素

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用

KthLargest.add，返回当前数据流中第K大的元素。

示例:

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

说明:

你可以假设 nums 的长度≥ k-1 且k ≥ 1。

来源：力扣（LeetCode）

链接： 力扣…​

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import heapq
class KthLargest(object):

def __init__(self, k, nums):
    """
    :type k: int
    :type nums: List[int]
    """
    self.k = k
    self.nums = nums
    heapq.heapify(self.nums)
    while len(self.nums) > self.k:
        heapq.heappop(self.nums)

def add(self, val):
    """
    :type val: int
    :rtype: int
    """
    if val > self.nums[0]:
        heapq.heapreplace(self.nums, val)
        return self.nums[0]
    else:
        return self.nums[0]

Your KthLargest object will be instantiated and called as such:

obj = KthLargest(k, nums)

param_1 = obj.add(val)

def test_KthLargest():
k = 3
arr = [4,5,8,2]
kthlargest = KthLargest(k,arr)
assert kthlargest.add(3) == 4
assert kthlargest.add(5) == 5
assert kthlargest.add(10) == 5
assert kthlargest.add(9) == 8
assert kthlargest.add(4) == 8

if name == 'main':
k = 3
arr = [4,5,8,2]
kthlargest = KthLargest(k,arr)
print(kthlargest.add(3))
print(kthlargest.add(5))