LeetCode Top K Frequent Elements Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,3] and k = 2, return [1,2]. Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

---

本题要找出数组中出现频率最高的前k个数。要求时间复杂度低于O(nlgn)，所以直接对原始数组排序是不行的。 第一直觉是用hash，找到数字和频率的对应关系，然后对频率排序，取频率最高的前k个数。对频率的排序可以用最大堆，就是建立以频率为key的堆，然后不断从堆顶取数字，直到取够k个为止。 STL中的优先队列priority_queue就是一个最大堆；对pair进行排序时，优先对pair中的first排序，然后是second。 完整代码如下： [cpp] class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> hash; for (int i = 0; i < nums.size(); ++i) { ++hash[nums[i]]; } priority_queue<pair<int, int>> max_heap; for (unordered_map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) { max_heap.push({ it->second,it->first }); } vector<int> ans; for (int i = 0; i < k; i++) { ans.push_back(max_heap.top().second); max_heap.pop(); } return ans; } }; [/cpp] 本代码提交AC，用时59MS。 找到数字和频率的对应关系之后，还可以用桶排序找频率最高的前k个数字，其实相当于对频率再次hash。因为长度为n的数组中不同的频率最多有n个（应该到不了n个），至少是1个（即所有数都是一样的，则只有一个频数n），所以我们开一个长度为n的二维数组，一级下标对应频率，然后把相同频率的数扔到以频数为下标的桶里，最后从后到前遍历桶，也就是先遍历频数大的数，直到取到k个数位置。 完整代码如下： [cpp] class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> hash; for (int i = 0; i < nums.size(); ++i) { ++hash[nums[i]]; } vector<vector<int>> bucket(nums.size() + 1); for (unordered_map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) { bucket[it->second].push_back(it->first); } vector<int> ans; for (int i = bucket.size() – 1; k > 0 && i > 0; –i) { if (bucket[i].size() > 0) { for (int j = 0; j < bucket[i].size(); ++j) { ans.push_back(bucket[i][j]); –k; } } } return ans; } }; [/cpp] 本代码提交AC，用时29MS，果然比之前的快很多。]]>