最近都在恶补其他东西，有段时间没写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有关，知道的麻烦告诉我