最近都在惡補其他東西，有段時間沒寫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有關，知道的麻煩告訴我