This is the 11th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 11th day that I participated in the article of August, today I bring you the algorithm problem about binary tree is the KTH largest element in the data stream, the text is as follows:

The title

Design a class that finds the KTH largest element in the data stream. Notice that it’s the KTH largest element in the order, not the KTH different element.

Please realize KthLargest category:

  • KthLargest(int k, int[] nums) Initializes the object using integer K and integer stream nums.
  • Int add(int val) Returns the KTH largest element in the current data stream after inserting val into nums.

The sample

Input: [" KthLargest ", "add", "add", "add", "add", "add"] [[3] [4, 5, 8, 2], [3], [5], [10], [9], [4]] output: [null, 4, 5, 5, 5, 8, 8] 解 义 : largest 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 8Copy the code

Their thinking

TopK algorithm is often asked in interviews. The solution to this question is as follows:

  1. Use a small root heap of size K, and ensure that the number of elements in the heap does not exceed K when initializing.
  2. Each time you add(), push() a new element into the heap. If the number of elements in the heap exceeds K, pop() is needed to pop out the smallest element in the heap.
  3. The smallest element in the heap (the top of the heap) is the KTH largest element in the entire data stream.

In this case, I’m using a priority queue to store the first K elements, where the priority queue is headed by the smallest element in the queue, which is the KKTH largest element.

Code implementation

class KthLargest {
    // Only k values will be recorded forever
    PriorityQueue<Integer> pq;
    int k;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<Integer>();
        for (int i = 0; i < nums.length; i++) { add(nums[i]); }}public int add(int val) {
        pq.offer(val);
        // If the length of the queue exceeds K, the queue is ejected
        if(pq.size() > k){
            pq.poll();
        }
        // Return the KTH largest value
        returnpq.peek(); }}Copy the code

The last

Complexity analysis

  • Time complexity: The initialization time complexity is O(nlogk), where n is the length of NUMs during initialization. The single insertion time complexity is O(logk);

  • Space complexity: O(k). You need to use a priority queue to store the first k largest elements.