LeetCode Top K Frequent Elements

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,果然比之前的快很多。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *