LeetCode : Top K Frequent Elements

Solution - O(n)

vector<int> topKFrequent(vector<int>& nums, int k) { // 统计每个数字的频率 unordered_map<int, int> rec; for(int i = 0; i < nums.size(); i++) rec[nums[i]]++; // 按频率存放数字 vector<vector<int>> bucket(nums.size()); for (auto it : rec) bucket[it.second - 1].push_back(it.first); vector<int> res; for (int i = bucket.size() - 1; i >= 0 && k > 0; i--) { for (int temp : bucket[i]) res.push_back(temp); k -= bucket[i].size(); } return res; }