LeetCode 347——前K个高频元素

一、题目介绍

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

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

说明：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

二、解题思路

本题难点在于时间复杂度由于O(nlog n)。

（1）遍历一遍数组，利用哈希映射map可以在O(n)的时间复杂度内，确定每个元素的出现次数。

（2）将map中的每个元素放入优先队列（即大顶堆）中，可以在log n的时间复杂度内，根据出现次数完成降序排列。

（3）将优先队列的前K个元素取出。总的时间复杂度O(n + log n + k) ≈ O(n)

三、解题代码

struct cmp  //比较函数
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second < b.second;    //降序排列
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> mp;
        for(int i = 0; i < nums.size(); ++i)
        {
            mp[nums[i]]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> v(mp.begin(), mp.end());  //初始化优先队列
                
        vector<int> res;
        for(int i = 0; i < k; ++i)
        {
            res.push_back(v.top().first);
            v.pop();
        }
        return res;
    }
};
           

四、解题结果