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.使用unordered_map和PRiority_queue，時間復雜度O(n*lg(n-k))。
class Solution {public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> ump; for(auto num : nums) ump[num]++; vector<int> res; priority_queue<pair<int, int>> pq; for(auto it : ump){ pq.push(make_pair(it.second, it.first)); //pair<first, second>, in priority_queue ths first is frequency, second is number if(pq.size() > ump.size() - k){ res.push_back(pq.top().second); pq.pop(); } } return res; }};新聞熱點
疑難解答
