Halo

A magic place for coding

0%

LeetCode 解题报告(100)-- 347. Top K Frequent Elements

Problem

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

Example 1:

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

Example 2:

1
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 (n log n), where n is the array’s size.
  • It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
  • You can return the answer in any order.

Analysis

   这道题目是关于数字频率统计的,这种统计常规的做法是用 map 统计。而这道题目比较难的是有一个排序,要找出出现频率前 k 个高的。既然用到排序,就是用 priority_queue,以出现的频率作为 key,以数字本身作为 value。插入到 queue 里面后,就已经排好序了,之后输出前 k 个就可以了。


Solution

   直接使用 C++ 提供的 unorder_map 和 priority_queue 即可。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
priority_queue<pair<int, int>> q;
vector<int> res;

int size = nums.size ();

for (int i = 0; i < size; i++) {
m [nums [i]]++;
}

for (auto it : m) q.push ({it.second, it.first});
for (int i = 0; i < k; ++i) {
res.push_back (q.top ().second);
q.pop ();
}
return res;
}
};

Summary

   这道题目的难度是 medium,实际的思路不难,但要求对一些数据结构的使用比较熟悉。如果对 C++ 的一些 stl 容器比较熟悉的话,这道题就能快速解决了。希望这篇博客能够帮助到您,感谢您的支持,欢迎转发、分享、评论,谢谢!

Welcome to my other publishing channels