LeetCode347—Top K Frequent Elements

Myth丶恋晨 2022-08-21 13:39 139阅读 0赞

# LeetCode347—Top K Frequent Elements #

五一刚收假，状态不是很好，赶紧刷个题恢复一下技术。

## 原题 ##

> Given a non-empty array of integers, return the k most frequent elements.
> 
> For example,  
> Given `[1,1,1,2,2,3]` and `k = 2`, return `[1,2]`.

## 分析 ##

题目中的示例输入输出给的不是很好，但题目意思还算比较清晰。就是说找出容器中出现次数排行前K的数，所以说需要以下几步：  
1. 统计出容器中每个元素出现的次数  
2. 对容器按照出现次数进行排序（从大到小）  
3. 取排好序的前K个元素即可。

思路很简单就是要选择数据结构和算法了：  
1. 数据结构的话，可以使用map和pair来建立元素和个数的一一对应关系。  
2. 题目中说要求时间复杂度在O(nlogn)，那对我们的排序算法就有要求，考虑到平均复杂度为O(nlogn)常见的就是堆排序和归并排序了（这里考虑到快排在最坏情况下时间复杂度为O(n2)）。

我们知道优先级队列的底层实现和堆排序类似，默认情况下是大顶堆。这样的话事实上就偷了个懒，不用我们写排序算法，将元素插入优先队列（设定元素的出现次数为优先级），然后对前K个元素出队即可。

**注：**  
这里有一点需要注意，虽然说是从大到小排序，但由于堆这种特殊结构，每次都是将根元素（堆中最大元素）换出堆，也就是说，如果使用优先级队列，每次出队的元素必然是优先级最高的，所以我们直接使用默认的大顶堆，从小到大排序即可。

### **代码** ###

class Solution {
    public:
        typedef pair<int, int> PAIR;
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int >count;
            for (int i = 0; i < nums.size(); i++)
            {
                count[nums[i]]++;//计数
            }
            //优先级队列默认是大顶堆（从小到大排序）
            //unordered_map默认按Key排序
            //因此优先级队列每次出队为最大值
            priority_queue<PAIR>tmpres;
            for (auto it = count.begin(); it != count.end(); it++)
            {
                tmpres.push(PAIR(it->second,it->first));//插入优先级队列
            }
            vector<int> result;//保存结果集
            for (int i = 0; i < k; i++)
            {
                result.push_back(tmpres.top().second); 
                tmpres.pop();
            }
            return result;
        }
    };