题目描述
Given a non-empty array of integers, return the k most frequent elements.
Example1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example2:
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.
最大堆解题思路
- 让统计前k个高频的数字，那么对于这类的统计数字的问题，首先应该考虑用 HashMap 来做，建立数字和其出现次数的映射，unordered_map实现
- 然后再按照出现次数进行排序。可以用堆排序来做，使用一个最大堆来按照映射次数从大到小排列，在 C++ 中使用 priority_queue 来实现，默认是最大堆，
C++代码
class Solution {
public:
static bool cmp(const pair<int, int>& mmap1, const pair<int, int >& mmap2){
return mmap1.second > mmap2.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mmap;
for(int i = 0 ; i < nums.size(); i++){
mmap[nums[i]]++;
}
priority_queue<pair<int, int>> q; // 元素也是一个一个的pair
for(auto &i : mmap){
q.push(make_pair(i.second, i.first)); // 这样就按照第二个关键字进行排序了
}
vector<int> res;
for(int i = 0; i < k; i++){
res.push_back(q.top().second); // q.top() 取到按照second进行排序的最大元素
q.pop(); // 记得执行pop操作
}
return res;
}
};
重新cmp函数解题思路
- 使用unordered_map解题思路
- 首先 unordered_map, map这种键值对容器是不支持直接sort的，需要将其pair元素push到序列化容器中
- 在C++里类重写cmp函数，这个cmp函数应该是静态的 即 static bool cmp
- cmp的参数也要注意，应该是 const pair<int, int>& a, const pair<int, int>& b 这个形参只能是pair，不能是unordered_map
- 取值的时候，有两种方法，iter -> second / (*iter).second 等等
- 如果取到的元素是pair本身，那么直接用 . 运算符即可取到元素
C++代码
class Solution {
public:
static bool cmp(const pair<int, int>& mmap1, const pair<int, int >& mmap2){
return mmap1.second > mmap2.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mmap;
for(int i = 0 ; i < nums.size(); i++){
mmap[nums[i]]++;
}
// sort(mmap.begin(), mmap.end(), cmp); // map,unordered_map中的元素是以pair类存在，不支持排序
vector<pair<int, int>> v_mmap;
for(auto &i : mmap){
v_mmap.push_back(i); // 将其转换成vector容器，下面进行排序
}
stable_sort(v_mmap.begin(), v_mmap.end(), cmp);
vector<int> res;
for(int i = 0; i < k; i++){
res.push_back(v_mmap[i].first); ** // v_mmap 其实是具体的pair，如果是取到具体的pair的话，用.运算符，如果使用迭代器来遍历元素额话，则使用 -> 运算符 **
}
return res;
}
};
C++代码
class Solution {
public:
static bool cmp(pair<int, int> &p1, pair<int, int>& p2){
return p1.second > p2.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
if(k > nums.size()){
return {};
}
vector<int> res;
unordered_map<int, int> mmap;
for(auto& i : nums){
mmap[i]++;
}
vector<pair<int ,int>> vec(mmap.begin(), mmap.end());
sort(vec.begin(), vec.end(), cmp);
for(int i = 0; i < k; i++){
res.push_back(vec[i].first);
}
return res;
}
};
