力扣日記：【棧與隊列篇】前 K 個高頻元素

日期：2023.10.31
參考：代碼隨想錄、力扣

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

進階：你所設計算法的時間復雜度 必須 優(yōu)于 O(n log n) ，其中 n 是數組大小。

題解

class Solution {
#define SOLUTION 2
public:vector<int> topKFrequent(vector<int>& nums, int k) {
#if SOLUTION == 1// 時間復雜度: O(n) + O(n) + O(nlogn) + O(k) = O(nlogn)// 空間復雜度: O(n+n)unordered_map<int, int> cnt;for (const auto& n: nums) {cnt[n]++;}// 將哈希表的內容復制到 vector// 使用迭代器范圍構造函數（iterator range constructor）創(chuàng)建 sortedVector// 這個構造函數接受兩個迭代器，它會遍歷 cnt 中的元素，然后復制它們到 sortedVector 中vector<pair<int, int>> sortedVector(cnt.begin(), cnt.end());// 按第二個值的大小對 vector 進行排序(從大到小)sort(sortedVector.begin(), sortedVector.end(), [](const pair<int, int>& a, const pair<int, int>& b) { // 匿名函數作為比較器參數return a.second > b.second; // 前者大于后者時返回true，表示前者應該在后者前面（大在前、小在后）});// 取前k個元素int count = 0;vector<int> result;for (const auto& pair : sortedVector) {result.push_back(pair.first);count++;if (count >= k) break;}return result;}
#elif SOLUTION == 2// unordered_map + 小頂堆// O(nlogk), O(n+k)// 之所以用堆，是因為沒必要對n個元素都進行排序，只需要維護前k個元素即可// 1. 首先用map遍歷一遍數組，確定每個數出現的頻率unordered_map<int, int> cnt;for (const auto& n: nums) {cnt[n]++;}// 2. 使用小頂堆遍歷map，維護出現頻率最高的前k個元素// 小頂堆：本質是一個二叉樹，每個父結點的值小于子結點，即根結點的值是最小的，值從小到大排列// 關于為什么用小頂堆而不是用大頂堆：/*如果是大頂堆的話，由于其僅維護k個元素，每次push進元素時都需要pop掉根結點元素而根結點是值最大的元素，這樣的話會導致最后大頂堆中都是出現頻率最低的前k個元素所以要用小頂堆，每次pop元素彈出值最小的元素，維護出現頻率最高的前k個元素*/// 小頂堆通過優(yōu)先級隊列實現priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小為k的小頂堆，掃面所有頻率的數值for (unordered_map<int, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {pri_que.push(*it); // 把it指向的<key,value>放進隊列if (pri_que.size() > k) { // 如果堆的大小大于了K，則隊列彈出，保證堆的大小一直為kpri_que.pop();}}// 3. 找出前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 mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second; // 為什么是>(大的在前，小的在后???)}};
#endif
};

復雜度

• 哈希map + 快排：
  • 時間復雜度：O(nlogn)
  • 空間復雜度：O(n)
• 哈希map + 小頂堆
  • 時間復雜度：O(nlogk)
  • 空間復雜度：O(n)

思路總結

• 解法1：哈希map + 快排
  • 哈希map不能直接排序，要轉換為vector才能進行排序
    • 1.將哈希表的內容復制到 vector
    • 2.使用迭代器范圍構造函數（iterator range constructor）創(chuàng)建 sortedVector
      • 這個構造函數接受兩個迭代器，它會遍歷 cnt 中的元素，然后復制它們到 sortedVector 中
      • vector<pair<int, int>> sortedVector(cnt.begin(), cnt.end());
    • 3.按第二個值的大小對 vector 進行排序(從大到小)

    sort(sortedVector.begin(), sortedVector.end(), [](const pair<int, int>& a, const pair<int, int>& b) { // 匿名函數作為比較器參數return a.second > b.second; // 前者大于后者時返回true，表示前者應該在后者前面（大在前、小在后）});
    

• 解法2：哈希map + 小頂堆
  • 之所以用小頂堆而不用快排，是因為沒必要對n個元素都進行排序，只需要維護前k個元素即可（快排需要對n個元素進行排序，O(nlogn)，小頂堆每次pop和push一個元素只需要logk，即對所有元素的總時間復雜度為O(nlogk)
  • 思路步驟：
  • 1.首先用map遍歷一遍數組，確定每個數出現的頻率
  • 2.使用小頂堆遍歷map，維護出現頻率最高的前k個元素
    • 小頂堆：本質是一個二叉樹，每個父結點的值小于子結點，即根結點的值是最小的，值從小到大排列
    • 關于為什么用小頂堆而不是用大頂堆：
      如果是大頂堆的話，由于僅維護k個元素，每次push進元素時都需要pop掉根結點元素
      而根結點是值最大的元素，這樣的話會導致最后大頂堆中都是出現頻率最低的前k個元素
      所以要用小頂堆，每次pop元素彈出值最小的元素，維護出現頻率最高的前k個元素
    • 小頂堆通過優(yōu)先級隊列實現：其中比較器設置為"左值>右值"（可能與優(yōu)先級隊列的底層實現有關）—— 注意這與快排cmp是相反的，快排cmp“左值>右值"是從大到小降序排列，而優(yōu)先級隊列"左值>右值"是小頂堆（根小子大）
  • 3.找出前K個高頻元素，因為小頂堆先彈出的是最小的（取first即元素的鍵），所以倒序來輸出到數組
• 學會小頂堆的實現以及小頂堆遍歷的寫法：

// 小頂堆實現
class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};
// 優(yōu)先級隊列定義與遍歷
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 參數1：優(yōu)先級隊列的元素類型，參數2：優(yōu)先級隊列自身類型，參數3：優(yōu)先級隊列的比較器（決定是小頂堆還是大頂堆）
for (unordered_map<int, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {pri_que.push(*it); // 把it指向的<key,value>放進隊列if (pri_que.size() > k) { // 如果堆的大小大于了K，則隊列彈出，保證堆的大小一直為kpri_que.pop();}
}