题目解析
从数组中找到出现频率前K多的元素
方法一 排序
使用map来获得所有元素的频率,然后排序,找到前k个元素。时间复杂度是O(nlgn) 耗时20ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> counts; vector<int> result; vector<pair<int, int>> numsAndCount; for (int num: nums) { counts[num]++; } for (auto it: counts) { numsAndCount.push_back(it); } sort(numsAndCount.begin(), numsAndCount.end(), [](auto &a, auto &b){return a.second < b.second;}); for (int i = 0; i < k; i++) { result.push_back(numsAndCount.back().first); numsAndCount.pop_back(); } return result; } };
|
方法二 大根堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> counts; vector<int> result; auto cmp = [](auto &a, auto &b){return a.second < b.second;}; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> numsAndCount(cmp); for (int num: nums) { counts[num]++; } for (auto it: counts) { numsAndCount.push(it); } for (int i = 0; i < k; i++) { result.push_back(numsAndCount.top().first); numsAndCount.pop(); } return result; } };
|