0%

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

题目描述

题目链接:Top K Frequent Elements

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.

解题思路

这道题可以分为两部分:计算各元素的出现频率,选出频率前 k 的元素。这两部分都比较简单,可以用哈希表来计算频率统计的计算,而用优先队列来筛选频率前 k 高的元素。注意一下对非标准元素的优先队列的使用方法即可(这里是 std::pair<int, int>)。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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