Re: [閒聊] 每日LeetCode已回收
看板Marginalman作者Neuenmuller (蘇菲・諾伊恩謬拉)時間2年前 (2023/05/23 06:55)推噓2(2推 0噓 0→)留言2則, 2人參與討論串325/719 (看更多)
最近都在惡補其他東西，有段時間沒寫Leetcode了
也來寫寫看
這個先用priority_queue來算有每個數字出現幾次
然後
A. 全部dump到vector裡sort
B. 放到heap裡面
來取出現最多次的數字
A.
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> bin;
for (int n: nums) bin[n]++;
vector<pair<int, int>> dump(bin.begin(), bin.end());
sort(dump.begin(), dump.end(), [](auto lhs, auto rhs)->bool {
return lhs.second > rhs.second;
});
vector<int> result;
for (int i = 0; i < k; i++) result.push_back(dump[i].first);
return result;
}
B. 原本我直接塞到max heap裡面，然後取最大k個
但是看到了一個用min heap的，在push的過程超過k個就踢掉top的做法覺得不錯
大概可以省最後pop的時間跟記憶體ㄅ
vector<int> topKFrequent(vector<int>& nums, int k) {
using binIt = unordered_map<int, int>::iterator;
unordered_map<int, int> bin;
for (int n: nums) bin[n]++;
// min-heap
priority_queue<binIt, vector<binIt>, function<bool(binIt, binIt)>> heap
([](binIt lhs, binIt rhs) -> bool {
return lhs->second > rhs->second;
},
vector<binIt>());
for (binIt it = bin.begin(); it != bin.end(); it++) {
heap.push(it);
if (heap.size() > k) heap.pop();
}
vector<int> result;
while (!heap.empty()) {
result.push_back(heap.top()->first);
heap.pop();
}
return result;
}
但是跑出來B的解法比較慢一點，不太確定原因
到這邊我就懶了，不太想自己在local慢慢測試leetcode結果runtime為啥會這樣
第一個想法覺得搞不好跟cache有關，知道的麻煩告訴我
--
ありがとうございます、お優しいルナ様
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 169.235.95.219 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1684796138.A.78F.html
※ 編輯: Neuenmuller (169.235.95.219 美國), 05/23/2023 06:58:18
推
05/23 07:08,
2年前
, 1F
05/23 07:08, 1F
推
05/23 07:21,
2年前
, 2F
05/23 07:21, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 325 之 719 篇)：