Problem
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
1 | Input: nums = [1,1,1,2,2,3], k = 2 |
Example 2:
1 | Input: nums = [1], k = 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 | class Solution { |
Summary
这道题目的难度是 medium,实际的思路不难,但要求对一些数据结构的使用比较熟悉。如果对 C++ 的一些 stl 容器比较熟悉的话,这道题就能快速解决了。希望这篇博客能够帮助到您,感谢您的支持,欢迎转发、分享、评论,谢谢!