# LeetCode347. Top K Frequent Elements（模拟）

## LeetCode347. Top K Frequent Elements（模拟）

• Medium
• Accepted：191,936
• Submissions：354,049

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than $O(nlogn)$, where n is the array's size.

### 链接

https://leetcode.com/problems/top-k-frequent-elements

### 代码

Time SubmittedStatusRuntimeMemoryLanguage
5 hours agoAccepted20 ms11.4 MBcpp
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector <int> ret;
unordered_map <int, int> umap;
int n = nums.size();
for (int i = 0; i < n; ++i)
umap[nums[i]]++;
priority_queue<pair<int, int> > pq;
for (auto it = umap.begin(); it != umap.end(); ++it)
{
pq.push(make_pair(it->second, it->first));
if (pq.size() > umap.size() - k)
{
ret.push_back(pq.top().second);
pq.pop();
}
}
return ret;
}
};

The end.
2019年4月17日 星期三