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.

本题最快解法是利用hashmap统计每个num的frequency,然后遍历hashmap插入priority queue(最小堆)中,最后根据要求的k个最大将min不断从堆中pop出来就好了。时间复杂度O(klogk)。

Solution:

 


class Solution {
public:
		unordered_map<int, int> freqMap;
		priority_queue<pair<int, int>> freqQueue;
		vector<int> freqVec;

		vector<int> topKFrequent(const vector<int>& nums, int k) {
			    	vector<int> res(k, 0);
				int size = nums.size();
				for (int i = 0; i < size; ++i)
				{
					    freqMap[nums[i]] += 1;
				}
        			for(auto it = freqMap.begin(); it != freqMap.end(); ++it)
        			{
				            freqQueue.emplace(it->second, it->first);
			        }
        
			        for(int i = 0; i < k; i++)
			        {
				            res[i] = freqQueue.top().second;
				            freqQueue.pop();
			        }
				return res;
		}
};
36ms

Leave a Reply

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