LeetCode 熱題 100_前 K 個高頻元素（73_347_中等_C++）(堆)(哈希表+排序；哈希表+優先隊列（小根堆）)

LeetCode 熱題 100_前 K 個高頻元素（73_347）

- 題目描述：
- 輸入輸出樣例：
- 題解：
- - 解題思路：
  - - 思路一（哈希表+排序）：
    - 思路二（哈希表+優先隊列（小根堆））：
  - 代碼實現
  - - 代碼實現（思路一（哈希表+排序））：
    - 代碼實現（思路二（哈希表+優先隊列（小根堆）））：
    - 以思路二為例進行調試
    - 部分代碼解讀

題目描述：

給你一個整數數組 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⁵
k 的取值范圍是 [1, 數組中不相同的元素的個數]
題目數據保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的

題解：

解題思路：

思路一（哈希表+排序）：

1、創建一個哈希表，key來存儲數組中元素，value存儲對應key出現的次數。對value進行快速排序。提取排序后，前k個元素的值。

2、復雜度分析：
① 時間復雜度：O(nlogn)，n為數組中元素的個數
????遍歷 nums 數組中的每個元素，將其出現的頻率存儲到 unordered_map 中。這個過程的時間復雜度是 O(n)。
????將 unordered_map 的元素復制到 vector 中，這個操作的時間復雜度是 O(n)。
????對 tmp 中的元素進行排序，排序的時間復雜度是 O(n log n)。
????從排序后的 tmp 中選擇前 k 個元素并將它們添加到 ans 中，這個過程的時間復雜度是 O(k)。
② 空間復雜度：O(n + log n)，除返回答案的空間外，unordered_map 的空間復雜度是 O(n)，vector<pair<int, int>> tmp 的空間復雜度是 O(n)。快速排序，空間復雜度是 O(log n)

思路二（哈希表+優先隊列（小根堆））：

1、創建一個哈希表，key來存儲數組中元素，value存儲對應key出現的次數。創建可以維持 k 個元素的小根堆（根據value大小進行插入），這樣在插入元素大于 k 時可以將堆頂的元素移出（優先級隊列就是一個披著隊列外衣的堆）。

2、復雜度分析
① 時間復雜度：O(n log k)，其中 n 是輸入數組的長度，k 是要求的前 k 個頻率最高的元素。遍歷 nums 數組并將每個元素的出現頻率存入 unordered_map中為 O(n)。將元素插入最小堆O(n log k)。從堆中彈出元素并構建結果數組 O(k log k)。
② 空間復雜度： O(n + k)，哈希表存儲每個數字及其頻率，最壞情況下需要存儲所有 n 個數字 O(n)。最小堆的最大大小為 O(k)。

代碼實現

代碼實現（思路一（哈希表+排序））：

class Solution1 {
public:// 函數接受一個整數數組 nums 和一個整數 k， 返回出現頻率最高的 k 個元素vector<int> topKFrequent(vector<int>& nums, int k) {// 使用 unordered_map 來統計每個數字出現的頻率unordered_map<int,int> count;// 遍歷 nums 數組，統計每個數字的出現次數for (int &num : nums){count[num]++; // 每遇到一個 num，就將對應的頻率加 1}// 將 unordered_map 中的元素復制到一個 vector 中，以便進行排序vector<pair<int,int>> tmp(count.begin(), count.end());// 對 tmp 中的元素進行排序，按照頻率降序排序// 使用 lambda 表達式作為排序規則sort(tmp.begin(), tmp.end(), [](pair<int,int>& a, pair<int,int>& b) { return a.second > b.second; // 如果 a 的頻率大于 b 的頻率，返回 true });// 創建一個結果 vector 來存放出現頻率最高的 k 個元素vector<int> ans;// 選擇排序后的前 k 個元素的第一個值（即數字）到 ans 中for (int i = 0; i < k; i++){ans.emplace_back(tmp[i].first); // 將 tmp 中的第 i 個元素的第一個值添加到 ans}return ans; // 返回結果}
};

代碼實現（思路二（哈希表+優先隊列（小根堆）））：

class Solution2 {
private:// 自定義比較器類，用于堆的排序class Compare {public:// 重載比較運算符，按照頻率（second）大小進行比較bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {// 如果左邊的頻率大于右邊，返回true。這樣堆中頻率小的元素會排在堆頂。return lhs.second > rhs.second;}};public:// topKFrequent 函數返回數組中出現頻率前k大的元素vector<int> topKFrequent(vector<int>& nums, int k) {// 使用 unordered_map 來存儲每個元素及其出現的頻率unordered_map<int, int> count;// 統計數組中每個元素的出現次數for (int i = 0; i < nums.size(); i++) {count[nums[i]]++;}// 創建一個最小堆來保存頻率前 k 大的元素// priority_queue 的第三個參數是自定義的比較器 Compare，確保堆頂是頻率最小的元素priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> min_head;// 遍歷計數哈希表，將每個元素（和其頻率）加入到堆中for (auto& i : count) {min_head.push(i); // 將元素及其頻率壓入堆// 如果堆的大小超過了 k，則彈出堆頂元素（頻率最小的元素）if (min_head.size() > k) {min_head.pop();}}// 用來存儲最終的前 k 個頻率最大的元素vector<int> ans(k);// 從堆中依次彈出元素，存入答案數組// 由于堆頂是頻率最小的元素，因此我們從堆頂彈出并將元素存入結果數組for (int i = k - 1; i >= 0; i--) {ans[i] = min_head.top().first; // 獲取堆頂元素的值（即數字）min_head.pop(); // 彈出堆頂元素}return ans; // 返回包含頻率前 k 大的元素的數組}
};

以思路二為例進行調試

#include<iostream>
#include <vector>
#include<unordered_map>
#include<algorithm>
#include <queue>
using namespace std;class Solution2 {
private:// 自定義比較器類，用于堆的排序class Compare {public:// 重載比較運算符，按照頻率（second）大小進行比較bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {// 如果左邊的頻率大于右邊，返回true。這樣堆中頻率小的元素會排在堆頂。return lhs.second > rhs.second;}};public:// topKFrequent 函數返回數組中出現頻率前k大的元素vector<int> topKFrequent(vector<int>& nums, int k) {// 使用 unordered_map 來存儲每個元素及其出現的頻率unordered_map<int, int> count;// 統計數組中每個元素的出現次數for (int i = 0; i < nums.size(); i++) {count[nums[i]]++;}// 創建一個最小堆來保存頻率前 k 大的元素// priority_queue 的第三個參數是自定義的比較器 Compare，確保堆頂是頻率最小的元素priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> min_head;// 遍歷計數哈希表，將每個元素（和其頻率）加入到堆中for (auto& i : count) {min_head.push(i); // 將元素及其頻率壓入堆// 如果堆的大小超過了 k，則彈出堆頂元素（頻率最小的元素）if (min_head.size() > k) {min_head.pop();}}// 用來存儲最終的前 k 個頻率最大的元素vector<int> ans(k);// 從堆中依次彈出元素，存入答案數組// 由于堆頂是頻率最小的元素，因此我們從堆頂彈出并將元素存入結果數組for (int i = k - 1; i >= 0; i--) {ans[i] = min_head.top().first; // 獲取堆頂元素的值（即數字）min_head.pop(); // 彈出堆頂元素}return ans; // 返回包含頻率前 k 大的元素的數組}
};int main(int argc, char const *argv[])
{vector<int> nums={1,1,1,2,2,3};int k=2;Solution2 s2;vector<int> ans=s2.topKFrequent(nums,k);cout<<"[";for (int i = 0; i < ans.size(); i++){cout<<ans[i];if (i!=ans.size()-1){cout<<",";}}cout<<"]";return 0;
}

部分代碼解讀

比較器是 lambda 表達式

sort(tmp.begin(), tmp.end(), [](pair<int,int>& a, pair<int,int>& b) { return a.second > b.second; // 如果 a 的頻率大于 b 的頻率，返回 true 
});

最常見的比較器是 lambda 表達式，因為它：
非常簡潔，適用于大多數場景，特別是排序、查找等常用算法。
可以在需要時動態定義比較邏輯，而不需要額外定義函數或類。

Compare:自定義比較器類 (Functor)

class Compare {
public:// 重載比較運算符，按照頻率（second）大小進行比較bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {// 如果左邊的頻率大于右邊，返回true。這樣堆中頻率小的元素會排在堆頂。return lhs.second > rhs.second;}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> min_head;

Compare:自定義比較器類 (Functor)
pair<int, int> 是一個由兩個 int 類型元素組成的模板類，它可以存儲一對值。
這里的 vector<pair<int, int>> 表示堆的底層容器是一個 pair<int, int> 類型的 vector。
優點:
復用性強：可以在多個地方使用相同的比較邏輯，不需要每次都重新定義。
性能較好：在某些情況下，函數對象（類）可能比 lambda 表達式稍微高效，因為它可以在編譯時優化。
適合復雜邏輯：當比較邏輯較復雜時，使用類比 lambda 更加清晰和易于管理。
缺點:
代碼較多：需要定義一個額外的類，增加了代碼的復雜性，尤其是對于簡單的比較。

LeetCode 熱題 100_前 K 個高頻元素（73_347)原題鏈接
歡迎大家和我溝通交流(????)