設計一個找到資料流中第 k 大元素的類（class），注意是排序后的第 k 大元素，不是第 k 個不同的元素，
請實作 KthLargest 類：
KthLargest(int k, int[] nums) 使用整數 k 和整數流 nums 初始化物件，
int add(int val) 將 val 插入資料流 nums 后，回傳當前資料流中第 k 大的元素，
示例：
輸入：
[“KthLargest”, “add”, “add”, “add”, “add”, “add”]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
輸出：
[null, 4, 5, 5, 8, 8]
解釋：
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
提示：
1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
最多呼叫 add 方法 104 次
題目資料保證，在查找第 k 大元素時，陣列中至少有 k 個元素
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路：
這道題目需要反復閱讀才能夠理解真正的意思，就是先初始化一個類保存陣列，這個陣列只維護排名前K名的數字，允許重復，然后不斷添加，不斷洗掉小的元素，所以可以用最小堆或者multiset，允許重復的set，set會自動根據大小進行排序，代碼如下：
class KthLargest {
int K;
multiset<int> st;
public:
KthLargest(int k, vector<int>& nums) {
for (int n : nums) {
st.insert(n);
if (st.size() > k) st.erase(st.begin());
}
K = k;
}
int add(int val) {
st.insert(val);
if (st.size() > K) st.erase(st.begin());
return *st.begin();
}
};
/*作者：heroding
鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/solution/zui-xiang-xi-zhu-jie-by-heroding-h195/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，*/
heap代碼如下：
class KthLargest {
int len;
// 定義堆，根據>排序，即誰大誰在后面，最小堆可以理解為從小到大排序的佇列
priority_queue<int, vector<int>, greater<int>> heap;
public:
KthLargest(int k, vector<int>& nums) {
for (auto n : nums) {
heap.push(n);
// 如果超出K
if (heap.size() > k) {
heap.pop();
}
}
len = k;
}
int add(int val) {
heap.push(val);
// 如果超出K
if (heap.size() > len) {
heap.pop();
}
// 回傳堆頂
return heap.top();
}
};
/*作者：heroding
鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/solution/zui-xiang-xi-zhu-jie-by-heroding-h195/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/258966.html
標籤：其他
上一篇：HTML，CSS中的復合寫法總結