LeetCode_347_前K个高频元素

题目描述：

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

示例：

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

输入: nums = [1], k = 1
输出: [1]

提示：
1. 1 <= nums.length <= 10^5
2. k 的取值范围是 [1, 数组中不相同的元素的个数]
3. 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

解法1：堆排序

//小顶堆排序
//时间复杂度：O(nlogk)，空间复杂度：O(n)
class Solution {
public:

    //自定义小顶堆内的排序方式
    class mycomparison {
    public:
        bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs) {

            //我们的目的是让小顶堆按照值也就是频率排序，优先弹出频率最小的
            return lhs.second > rhs.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {

        vector<int> ans;  //返回的结果
        unordered_map<int,int> map;  //定义一个哈希表，统计元素出现的频率

        for (int i = 0; i < nums.size(); i++) ++map[nums[i]];

        //定义一个小顶堆
        //因为要统计前k个高频元素，小顶堆每次都会将最低频的元素弹出，小顶堆中剩余的就是高频元素
        priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison > q;

        //⭐️小顶堆默认按照键来排序，所以我们需要自己定义排序方式
        //priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > q;

        for (auto &a : map) {

            q.push(a);  //⭐️小顶堆内存放的是哈希表内的键值对

            if (q.size() > k) q.pop();  //如果堆的大小大于k，则优先队列弹出，保证堆的大小一直为k
        }

        //找出前k个高频元素
        for (int i = 0; i < k; ++i) {

            ans.push_back(q.top().first);  //将键值对中的键存放到容器中
            q.pop();
        }

        return ans;
    }
};

//大顶堆排序
class Solution {
public:

    class mycomparison {
    public:
        bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs) {

            //优先弹出频率最大的
            return lhs.second < rhs.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {

        vector<int> ans;  
        unordered_map<int,int> map;  //定义一个哈希表，统计元素出现的频率

        for (int i = 0; i < nums.size(); i++) ++map[nums[i]];

        //定义一个大顶堆
        priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison > q;

        for (auto &a : map) q.push(a); 

        //找出前k个高频元素
        for (int i = 0; i < k; ++i) {

            ans.push_back(q.top().first);  //将键值对中的键存放到容器中
            q.pop();
        }

        return ans;
    }
};