LeetCode 347.前 K 个高频元素

题目描述

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

示例 1:

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

示例 2:

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

提示：

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

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

思路

本题主要有两个难点，一是如何求数组里每个元素出现的次数，二是如何对这个出现的次数进行排序，并求前k高频的元素。

求出现的次数可以使用map来进行记录，key存放元素，value存放出现的次数。

本题笔者的做法是将map转化为vector数组（使用pair）后再进行自定义排序。

不过，题目要求求的是前k个高频元素，我们其实没有必要对所有的元素进行排序，只需要维护k个有序的元素集合即可，比较经典的数据结构是大顶堆和小顶堆，它们擅长在大数据集里求前k个高频或者低频的元素。本题可以用堆去遍历map里的所有元素，让堆里维持k个元素，等遍历完成后，堆的k个元素就是前k个高频元素。如果维护的是大顶堆，那堆里维护的其实是前k个低频元素，因为堆是从堆顶pop元素的，而大顶堆的堆顶是最大的元素，这样每次都会将弹出大的元素。因此，本题应使用小顶堆，将小的元素全部pop出去，留下的就是前k个高频元素。

最后使用result数组存放从小顶堆中输出的元素时要让i从size-1开始，即倒序遍历result数组。

代码

C++版：

方法一：（笔者的做法：哈希表）

typedef pair<long long, int> PAIR; // 重命名pair
class Solution {
public:// 自定义比较函数static bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {  return lhs.second > rhs.second;  }  // 自定义函数对象，重载()，为sort()指定相应的Compare类struct CmpByValue {  bool operator()(const PAIR& lhs, const PAIR& rhs) {  return lhs.second > rhs.second;  }  };vector<int> topKFrequent(vector<int>& nums, int k) {// 哈希表法，使用map作为哈希表unordered_map<long long,int> m;vector<int> result;// 计数for(int i=0;i<nums.size();i++){if(m.find(nums[i])==m.end()){m[nums[i]]=1;}else{m[nums[i]]+=1;}}// 把unordered_map中的元素转存到vector中vector<PAIR> v(m.begin(),m.end());// 对map按value排序sort(v.begin(), v.end(),cmp_by_value); // sort(v.begin(), v.end(),CmpByValue()); // 取出前k个高频词for(int i=0;i<k;i++){result.push_back(v[i].first);}return result;}
};

方法二：（小顶堆）时间复杂度: 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) {// 先统计元素出现的次数unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆，大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆，扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};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) {// 先统计元素出现的次数unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆，大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆，扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};

Python版：

方法二：（小顶堆）

python">import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:#统计元素出现的次数sumMap = {} #nums[i]:对应出现的次数for i in range(len(nums)):sumMap[nums[i]] = sumMap.get(nums[i], 0) + 1#对出现的次数排序#定义一个小顶堆，大小为kpri_que = [] #小顶堆#用固定大小为k的小顶堆，扫描所有元素出现的次数for key, freq in sumMap.items():heapq.heappush(pri_que, (freq, key))if len(pri_que) > k: #如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kheapq.heappop(pri_que)#找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组result = [0] * kfor i in range(k-1, -1, -1):result[i] = heapq.heappop(pri_que)[1]return result

需要注意的地方

1.sort中的比较函数compare要声明为静态成员函数或全局函数，不能作为普通成员函数，否则会报错。

原因：非静态成员（non-static）函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法再sort中调用非静态成员函数。静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何对象实例就可以访问。

同时静态成员函数不可以调用类的非静态成员（因为非静态成员是依赖于对象的，有可能对象不存在，只有类存在，那就会出现错误）。一般来说就声明为main函数外面的全局函数，在力扣中就声明为static。

2.优先级队列是一种容器适配器，从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列，实际是堆，而且优先级队列内部元素是自动依照元素的权值排列。缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

3.堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。