347.前k个高频元素
小白解法
class Solution { public: static bool compare(const pair<int, int> &a, const pair<int, int> &b) { if (a.second == b.second) return a.first < b.first; else return a.second > b.second; } vector<int> topKFrequent(vector<int> &nums, int k) { map<int, int> Hash; for (int i = 0; i < nums.size(); i++) { if (!Hash.count(nums[i])) { Hash.emplace(nums[i], 1); } else { Hash[nums[i]]++; } } vector<pair<int, int>> v(Hash.begin(), Hash.end()); //将map中的元素拷贝到vector中 sort(v.begin(), v.end(), compare); vector<int> ans; for (int i = 0; i < k; i++) { ans.push_back(v[i].first); } return ans; } };
通过哈希表统计每个元素的出现频率，然后通过将map中的元素拷贝到vector中进行排序，得到前k个元素。快速排序时间复杂度O(nlogn)，不满足题目要求，需要优化。
易错点
类成员函数compare()需要static进行修饰。这是因为所有我们在类内定义的非static成员函数在经过编译后隐式的为他们添加了一个this指针参数！变为了：bool compare(Solution *this, int a, int b),而标准库的sort()函数的第三个cmp函数指针参数中并没有这样this指针参数，因此会出现输入的cmp参数和sort()要求的参数不匹配，从而导致了：error: reference to non-static member function must be called,而static静态类成员函数是不需要this指针的，因此改为静态成员函数即可通过！
优先队列（最小堆）
class Solution { public: class mycomparison { public bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs) { return lhs.second > rhs.second; } }; vector<int> topKFrequent(vector<int> &nums, int k) { unordered_map<int, int> map; for (int i = 0; i < nums.size(); i++) { map[nums[i]]++; } priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que; for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) { pri_que.push(*it); if (pri_que.size() > k) { pri_que.pop(); } } //最小堆先弹出最小的，所以倒叙输出 vector<int> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pri_que.top().first; pri_que.pop(); } return result; } };
先遍历一遍数组统计各元素出现频率，然后用一个最小堆，保证当堆的大小大于k时，最小值弹出，保证堆的大小一直是k。最后得到的就是前k个高频元素。最后，最小堆先弹出最小的，所以倒叙输出。
桶排序
class Solution { public: vector<int> topKFrequent(vector<int> &nums, int k) { // key=元素值, value=出现频率 unordered_map<int, int> counts; int maxCount = 0; for (int num : nums) { maxCount = max(maxCount, ++counts[num]); // 找到最大的频率 } vector<vector<int>> buckets(maxCount + 1); // 以出现频率为桶个数 for (auto p : counts) { buckets[p.second].push_back(p.first); } vector<int> ans; for (int i = maxCount; i > 0 && ans.size() < k; --i) { for (int num : buckets[i]) { ans.push_back(num); if (ans.size() == k) { break; } } } return ans; } };
首先通过哈希表统计每个元素的出现频率，然后以最大出现频率为桶个数，倒叙返回前k个元素。其实小白解法中的思想有类似之处，但小白使用的快排复杂度太高，这里的桶排序的复杂度只有O(n+k)。
