LeetCode 347前K個高頻元素

• 題目簡述：給定一個非空的整數數組，傳回其中出現頻率前 k 高的元素。注意：題目資料保證答案唯一，可以按任意順序傳回答案。

• 輸入：nums = [1,1,1,2,2,3], k = 2 輸出：[1,2]

  輸入：nums = [1], k = 1 輸出：[1]

• 思路：小根堆+哈希表

  使用哈希表統計每個數字出現的個數，然後維護一個大小為k的小根堆依次将哈希表中的元素和頻率加入，如果小根堆中元素個數超過了k，就将堆頂出現頻率較小的元素彈出，直到将哈希表元素周遊完，留在小根堆中的元素就是出現頻率前k高的元素。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for(auto x : nums) hash[x]++;//hash中<元素，頻率>
        //priority_queue<int, vector<int>, greater<int>> q; //定義小根堆
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;
        int i = 0;
        //小根堆優先以pair中的第一個元素為準排序
        for(auto &it : hash)
        {
            if(i < k)
            {
                i ++;
                q.push(make_pair(it.second,it.first));//pair中<頻率，元素>
            }
            else
            {
                if(it.second > q.top().first)
                {
                    q.pop();
                    q.push(make_pair(it.second,it.first));
                }
            }
        }
        vector<int> res;
        for(int i = 0 ; i < k ; i ++)
        {
            res.push_back( q.top().second );
            q.pop();
        }

        return res;
    }
};
           

• 計數排序+哈希表
  • 首先利用哈希表建立元素和頻率的映射關系，所有數出現的次數頻率都在 1到 n 之間
  • 再利用輸入數組大小的新數組

    vec

    統計每個頻率出現了多少次，數組下标表示頻率，如示例1中，共

    6

    個數，

    1

    出現

    3

    次，

    2

    出現

    2

    次，

    3

    出現

    1

    次，那麼

    vec=[0, 1, 1, 1, 0, 0, 0]

  • vec

    相當于按照頻率進行了排序，從頻率最高的開始統計一下出現次數為

    t

    次的元素各有多少個
  • 利用計數排序判斷出現前

    k

    多次的數字最少出現多少次，求出下界
  • 再周遊一次哈希表将所有出現次數大于等于這個下界的元素加入答案

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hash;//hash中<元素，頻率>
        for(auto x : nums) hash[x]++;
        int n = nums.size();
        vector<int> vec(n+1, 0);
        for(auto &it : hash) vec[it.second] ++;//統計每個頻率出現次數
        //for(auto y : vec) cout << y <<" ";//檢視vec數組
        int cnt = 0, t = n; 
        while(t--)
        {
            cnt += vec[t];
            if(cnt >= k) break;
        }
        //while(cnt < k) cnt += vec[t--];//類似寫法,僅需修改if(it.second > t)
        vector<int> res;
        for(auto &it : hash)      
            if(it.second >= t) res.push_back(it.first);
        return res;
    }
};