describe

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.

Implement KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
  • int add(int val) Returns the element representing the kth largest element in the stream.

Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8
Copy the code

Note:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • At most 104 calls will be made to add.
  • It is guaranteed that there will be at least k elements in the array when you search for the kth element.

parsing

It is easy to add val to nums and then reorder it to get the value of Kth. However, it can be time-consuming to add val to nums for thousands of times.

answer

class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.k = k
        self.nums = nums

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        self.nums.append(val)
        self.nums.sort()
        return self.nums[-self.k]
 
        	      
		
Copy the code

The results

Each node in the Python online submission is linked to a Stream. Memory Usage: 10000 ms. 10 MB, less than 10.91% of Python online submissions for Kth Largest Element in a Stream.Copy the code

answer

class KthLargest(object):

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

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len( self.nums ) < self.k:
            heappush(self.nums, val)
        else:
            heappushpop(self.nums, val)
        return self.nums[0]
Copy the code

The results

Each node in the Python online submission is linked to a Stream. Memory Usage: 10000 ms. Submissions for Kth Largest Element in a Stream.Copy the code

Original link: leetcode.com/problems/kt…

Your support is my biggest motivation