※ 引述《Neuenmuller (蘇菲・諾伊恩謬拉)》之銘言：
: 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();
: }
push 前加這個判斷看看
if (heap.size() < k || it->second > heap.top()->second){
heap.push(it);
if (heap.size() > k)
heap.pop();
}
python的話應該能直接改 heap[0] 然後 heapify
(*好像寫錯了 應該是要用 heappushpop() 或 heapreplace()
c++不知道可不可以
不過 leetcode 的 runtime 也蠻謎的
我同一份 code 跑出來時間常常都差很多 所以後來都不太看了
: vector<int> result;
: while (!heap.empty()) {
: result.push_back(heap.top()->first);
: heap.pop();
: }
: return result;
: }
: 但是跑出來B的解法比較慢一點，不太確定原因
: 到這邊我就懶了，不太想自己在local慢慢測試leetcode結果runtime為啥會這樣
: 第一個想法覺得搞不好跟cache有關，知道的麻煩告訴我