C++算法练习-day27——347.前k个高频元素

题目来源：. - 力扣（LeetCode）

题目思路分析

题目：找出数组中出现频率最高的前K个元素。

这个问题要求我们从给定的数组nums中找出频率最高的前k个元素。这通常意味着我们需要统计每个元素的出现次数，然后根据这些次数进行排序，并提取前k个元素。以下是解决这个问题的思路：

1. 统计频率：首先，我们需要统计每个元素在数组中出现的次数。这可以通过使用一个哈希表（如unordered_map）来实现，其中键是数组中的元素，值是该元素出现的次数。

2. 构建最小堆：接下来，我们需要一个数据结构来高效地获取频率最高的前k个元素。由于堆（特别是最小堆）可以在对数时间内插入和删除元素，并且总是保持堆顶元素为最小（或最大，取决于堆的类型），所以它是这个问题的理想选择。在这个问题中，我们将使用最小堆，但堆中的元素将按频率的负值排序（或者直接使用最大堆），以便堆顶始终是频率最高的元素。然而，为了简化，这里我们使用priority_queue配合自定义比较函数来实现最大堆的效果。

3. 维护堆的大小：在遍历哈希表时，我们将元素及其频率添加到堆中。如果堆的大小超过了k，我们就从堆中移除堆顶元素（当前频率最低的元素），以确保堆中始终只有频率最高的k个元素。

4. 提取结果：最后，我们从堆中提取元素，并将它们添加到结果数组中。由于堆是按照频率排序的，所以这些元素将按频率从高到低的顺序排列。

代码：

#include <vector>  
#include <unordered_map>  
#include <queue>  
#include <utility>  
  
using namespace std;  
  
class Solution {  
public:  
    // 自定义比较函数，用于构建最大堆  
    static bool cmp(pair<int,int>& m,pair<int,int>& n){  
        return m.second<n.second; // 注意这里使用小于号，因为我们传递给priority_queue的是cmp的指针，priority_queue默认是大顶堆，所以这里实现小顶堆的效果，但逻辑上我们视为最大堆（频率高的在上面）  
    }  
      
    vector<int> topKFrequent(vector<int>& nums, int k) {  
        unordered_map<int,int> pos; // 用于存储每个数字及其出现次数的哈希表  
        for(int& e:nums){  
            ++pos[e]; // 统计每个数字的出现次数  
        }  
          
        // 使用自定义比较函数cmp构建priority_queue（逻辑上视为最大堆）  
        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)> q(cmp);  
          
        // 遍历哈希表，将元素及其频率添加到堆中  
        for(auto& [num,count] : pos){  
            if(q.size()==k){  
                // 如果堆已满，检查当前元素频率是否高于堆顶元素频率  
                if(q.top().second<count){  
                    q.pop(); // 移除堆顶元素  
                    q.emplace(num,count); // 添加当前元素  
                }  
            }  
            else{  
                q.emplace(num,count); // 堆未满，直接添加当前元素  
            }  
        }  
          
        vector<int> ans; // 存储结果的数组  
        while(!q.empty()){  
            ans.push_back(q.top().first); // 提取堆顶元素（频率最高的元素）  
            q.pop(); // 移除堆顶元素  
        }  
          
        // 由于是从堆中逐个提取的，所以结果需要反转以恢复原始频率顺序（从高到低）  
        reverse(ans.begin(), ans.end()); // 但题目并未明确要求顺序，此步可省略  
          
        return ans; // 返回结果数组  
    }  
};

知识点摘要

1. 哈希表（unordered_map）：用于快速查找和统计元素的出现次数。
2. 堆（priority_queue）：用于高效地获取最大或最小元素，支持对数时间复杂度的插入和删除操作。
3. 自定义比较函数：用于在堆中根据元素的频率进行排序。
4. 范围for循环（for(auto& x : y)）：用于遍历容器中的元素。

本文介绍了如何使用哈希表和堆来解决找出数组中出现频率最高的前K个元素的问题。我们首先使用哈希表统计每个元素的出现次数，然后使用堆来维护频率最高的前K个元素。这种方法结合了哈希表的快速查找能力和堆的高效排序能力，是解决此类问题的有效方法。通过理解哈希表和堆的工作原理，以及如何自定义比较函数来构建堆，我们可以更好地解决类似的问题。