[Leetcode] Kth Largest Element in a Stream(Easy)

發表於： 分類於：
字數： 297 閱讀：≈ 1分鐘 瀏覽：

LeetCode 703 - Kth Largest Element in a Stream

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) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

example:

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

How can we solve this problem?

首先，我們要知道這個問題在問什麼。很簡單，這個問題問的是array中k個大元素。舉例 [1,2,3,4,5 ] k=3，需要我們求出三個最大的element，所以會是[3,4,5]。因此。我們只需要關心最大的K的element即可，其他都可以拋棄掉。

Solution: 

class KthLargest {
private:
    priority_queue<int,vector<int>,greater<int>> q;
    int k;
public:

    KthLargest(int k, vector<int>& nums) {
        for(auto e : nums) {
            q.push(e);
            if(q.size() > k) q.pop();
        }
        this->k = k;
    }
    
    int add(int val) {
        q.push(val);
        if(q.size() > k) q.pop();
        return q.top();
    }
};