Leecode---347：输出前k个高频元素（使用unordered_map）

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

思路：
三步：
1、用map来记录每个元素出现的次数
2、按map中的值大小排序，先让其有序，再逆序
3、输入前k个高频元素

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 统计元素出现的频率：unordered_map<key,value>
        unordered_map<int,int> mp;
        for(int i=0; i<nums.size();i++)
        {
            // 通过key值为nums[i]，给value值+1，value表示次数
            mp[nums[i]]++;
        }

        // 按值排序
        // pair作用是将两个数据组合成一个数据
        vector<pair<int,int>> vec;
        for(unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
        {
            // 当有必要对一个接受pair参数的函数传递两个值时，使用make_pair
            vec.push_back(make_pair(it->second, it->first));
        }
        sort(vec.begin(),vec.end());        // 升序排序
        reverse(vec.begin(),vec.end());     // reverse后，降序

        // 输出前 K 个高频
        vector<int> res;
        for(vector<pair<int, int>>::iterator it = vec.begin(); it != vec.begin()+k; it++)
        {
            res.push_back(it->second);
        }
        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