Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/12 09:02)推噓0(0推 0噓 0→)留言0則, 0人參與討論串696/1548 (看更多)
等補完課下午再來寫昨天的
題目: 703. Kth Largest Element in a Stream
設計一個class每次回傳stream中第k大的element，一開始的kthlargest會給定k和起始一
個代表stream的vector，之後的add(val) func會將val加入倒stream中，並回傳stream中
第k大的數字
思路:
這題可以很直觀用暴力法，一開始先sort好stream，之後每次add則是用upper_bound找出
val應該插在哪，插完後回傳第k大的數，但結果很爛，正確的解法應該是要保持一個k大
小的min heap根據val值判斷要直接回傳heap top還是pop後push val再回傳，注意的是
constraint是保證insert完能找到第k大，所以insert前當前heap可能為空
priority_queue<int, vector<int>, greater<int> > pre_ans;
int gg=0;
KthLargest(int k, vector<int>& nums) {
gg=k;
for(auto pp:nums){
if(pre_ans.size()<k){
pre_ans.push(pp);
}
else{
if(pp>pre_ans.top()){
pre_ans.pop();
pre_ans.push(pp);
}
}
}
}
int add(int val) {
if(pre_ans.size()<gg){
pre_ans.push(val);
return pre_ans.top();
}
if(val<=pre_ans.top()){
return pre_ans.top();
}
else{
pre_ans.pop();
pre_ans.push(val);
return pre_ans.top();
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.222.19 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723424579.A.6E7.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 696 之 1548 篇)：