## [Leetcode]347. Top K Frequent Elements(C++)

### 题目描述

Given an integer array `nums` and an integer `k`, return the `k` most frequent elements. You may return the answer in any order.

### 例子

#### 例子 1

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

#### 例子 2

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

### Constraints

• `1 <= nums.length <= 10^5`
• `k` is in the range `[1, the number of unique elements in the array]`.
• It is guaranteed that the answer is unique.

### 解题思路

``````#include <queue>
#include <unordered_map>

class Solution {
public:
std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
std::unordered_map<int, int> hmap;
for (int num : nums) {
if (hmap.find(num) == hmap.end()) {
hmap[num] = 1;
} else {
hmap[num]++;
}
}

using key_freq = std::pair<int, int>;
auto comp = [](const key_freq& lhs, const key_freq& rhs) {
return lhs.second >= rhs.second;
};
std::priority_queue<key_freq, std::vector<key_freq>, decltype(comp)> pq(
comp);

for (auto it : hmap) {
pq.push({it.first, it.second});
if (pq.size() > k) {
pq.pop();
}
}

std::vector<int> ret;
while (!pq.empty()) {
ret.push_back(pq.top().first);
pq.pop();
}

return ret;
}
};
``````
• 时间复杂度: `O(max(n, unique(nums) log k))` – 哈希表处理过程为 `O(n)`, 优先队列插入过程单次为 `O(log k)` 插入次数为数组中不重复元素的个数
• 空间复杂度: `O(n)`

GitHub 代码同步地址： 347.TopKFrequentElements.cpp

Built with Hugo
Theme Stack designed by Jimmy