※ 引述《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有关，知道的麻烦告诉我