题目描述
Given an integer array
nums
and an integerk
, return thek
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.
解题思路
这道题可以分为两部分:计算各元素的出现频率,选出频率前 k 的元素。这两部分都比较简单,可以用哈希表来计算频率统计的计算,而用优先队列来筛选频率前 k 高的元素。注意一下对非标准元素的优先队列的使用方法即可(这里是 std::pair<int, int>
)。代码如下:
#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
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions