Leecode: 347. 前 K 个高频元素_347ww

347-给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这里直接参考了官网的c++代码，很多c++语句自己都是第一次接触，这里记录下来积累一下

• C++11引入的for循环语句。

for (auto& a: num){} //(数据类型 变量：序列)

• C++11引入的vector的元素添加。

vector<int> a;
a.emplace_back(2);

1. 基于最小堆的方法

class Solution {
public:
    static bool cmp(pair<int,int>& m, pair<int,int>&n){
        return m.second>n.second;
    }

    vector<int> topKFrequent(vector<int>& nums,int k){
        unordered_map<int,int> occurance;
        for (auto& v:nums){
            occurance[v]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)> q(cmp); //C++ 优先队列函数，默认是大根堆，小根堆需要重写比较函数
        //定义
        for (auto&[num,count]:occurance){
            if(q.size()==k){
                if (q.top().second<count){
                    q.pop();
                    q.emplace(num,count);
                }

            }else{
                q.emplace(num,count);
            }
        }
        //赋值
        vector<int> res;
        while(!q.empty()){
            res.emplace_back(q.top().first);
            q.pop();
        }
        return res;
    }

};
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

基于桶排序的代码

class Solution{
    public:
    vector<int> topKFrequent(vector<int> nums,int k){
        vector<int> res;
        unordered_map<int,int> mp;       
        for(int i=0;i<nums.size();i++){
            mp[nums[i]]++;
        } 
        //开始桶排序 
        vector<vector<int>> bucket;    
        for(auto& r:nums){
            vector<int> temp;
            bucket.emplace_back(temp);
        }
         
        for(auto& [value,num]:mp){
            bucket[num-1].emplace_back(value);
        }
        
        int length=nums.size();
       
        for (int i=length-1;i>=0 && res.size()<k;i--){
            if(bucket[i].empty()) {continue;}
            for (auto& v:bucket[i]){
                 res.emplace_back(v);
            }  
        }
       
        return res;
    }
};
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

451. 根据字符出现频率排序

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
示例 1:

输入: s = “tree”
输出: “eert”
解释: 'e’出现两次，'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。
示例 2:

输入: s = “cccaaa”
输出: “cccaaa”
解释: 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-characters-by-frequency
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    static bool cmp(pair<char,int> m,pair<char,int>n){
        return m.second<n.second;
    }
    string frequencySort(string s) {
        unordered_map<char,int> q;
        for (auto& v:s){
            q[v]++;
        }
        priority_queue<pair<char,int>,vector<pair<char,int>>,decltype(&cmp)> pr(cmp);
        for (auto& [c,i]:q){
            pr.emplace(c,i);
        }

        cout<<pr.top().first<<endl;

        string res;
        while(!pr.empty()){
            int num=pr.top().second;
            char c=pr.top().first;
            for (int i=0;i<num;i++){
                res+=c;
            }
            pr.pop();
        }
        return res;
    }
};
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