LeetCode - Easy - 703. Kth Largest Element in a Stream

深藏阁楼爱情的钟 2022-10-11 12:11 160阅读 0赞

## Topic ##

*  Design
 *  Binary Search Tree
 *  Heap (Priority Queue)

## Description ##

[https://leetcode.com/problems/kth-largest-element-in-a-stream/][https_leetcode.com_problems_kth-largest-element-in-a-stream]

Design a class to find the  k t h k^\{th\} kth largest element in a stream. Note that it is the  k t h k^\{th\} kth largest element in the sorted order, not the  k t h k^\{th\} 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  k t h k^\{th\} 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

**Constraints:**

*   1 < = k < = 1 0 4 1 <= k <= 10^4 1<=k<=104
 *   0 < = n u m s . l e n g t h < = 1 0 4 0 <= nums.length <= 10^4 0<=nums.length<=104
 *   − 1 0 4 < = n u m s \[ i \] < = 1 0 4 -10^4 <= nums\[i\] <= 10^4 −104<=nums\[i\]<=104
 *   − 1 0 4 < = v a l < = 1 0 4 -10^4 <= val <= 10^4 −104<=val<=104
 *  At most  1 0 4 10^4 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  k t h k^\{th\} kth element.

## Analysis ##

使用优先队列实现。

## Submission ##

import java.util.PriorityQueue;
    
    public class KthLargestElementInAStream { 
    	public static class KthLargest { 
    
    	    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    	    private final int k;    
    	    public KthLargest(int k, int[] nums) { 
    	        this.k = k;
    	        for (Integer i : nums) { 
    	            minHeap.add(i);
    	            if (minHeap.size() > k) { 
    	                minHeap.poll();
    	            }
    	        }
    	    }
    	    
    	    public int add(int val) { 
    	        minHeap.add(val);
    	        if (minHeap.size() > k) { 
    	            minHeap.poll();
    	        }        
    	        return minHeap.peek();
    	    }
    	    
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.easy.KthLargestElementInAStream.KthLargest;
    
    public class KthLargestElementInAStreamTest { 
    
        @Test
        public void test() { 
    // KthLargestElementInAStream kObj = new KthLargestElementInAStream();
    
            KthLargest kthLargest = new KthLargest(3, new int[] { 4, 5, 8, 2});
            assertEquals(4, kthLargest.add(3));   // return 4
            assertEquals(5, kthLargest.add(5));   // return 5
            assertEquals(5, kthLargest.add(10));  // return 5
            assertEquals(8, kthLargest.add(9));   // return 8
            assertEquals(8, kthLargest.add(4));   // return 8
            
            
        }
    }

[https_leetcode.com_problems_kth-largest-element-in-a-stream]: https://leetcode.com/problems/kth-largest-element-in-a-stream/