目錄

• LeetCode 347：前 K 個高頻元素
• • 題目描述
  • 解題
  • • 哈希+排序
    • 哈希+優先隊列

LeetCode 347：前 K 個高頻元素

題目描述

給定一個非空的整數數組，傳回其中出現頻率前 k 高的元素。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2

輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1

輸出: [1]

提示：

你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。

你的算法的時間複雜度必須優于 O(n log n) , n 是數組的大小。bunengpai

題目資料保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的。

你可以按任意順序傳回答案。

解題

哈希+排序

    最直接的思路應該是對整個數組進行排序，這樣相同的數字相鄰，可以很輕松的統計每個數字出現的次數，但是算法要求複雜度優于 O ( n l o g n ) O(nlogn) O(nlogn)，是以直接排序是不可行的。但還是要統計每個整數的頻率，不能排序，那麼可以借助哈希表，這樣不用考慮數值範圍和各種取值可能。統計好之後按照次數再排序即可。

class Solution {
public:    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> nums_counts;
        for (auto &i : nums)
            ++nums_counts[i];
        
        vector<pair<int,int>> nums_counts_sort(nums_counts.begin(), nums_counts.end());
        sort(nums_counts_sort.begin(), nums_counts_sort.end(), [](pair<int, int> &a, pair<int, int> &b) { return a.second > b.second; });
        
        vector<int> topKF_nums(k, 0);
        for (int i=0; i < k; ++i)
            topKF_nums[i] = nums_counts_sort[i].first;
        return topKF_nums;
    }
};
           

哈希+優先隊列

    思路與哈希+排序本質是一緻的，隻不過借助優先隊列來排序和控制選擇的數目，優先隊列按照統計數從小到大存儲<統計數-數字>這一數對。統計好數字出現的次數之後，對哈希表進行周遊，如果優先隊列的大小小于k，則不斷将<統計數-數字>壓入隊列中，如果優先隊列大小等于k，且隊列頂部元素統計數小于目前元素統計數，則将頂部元素彈出，将該元素壓入隊列；如果隊列頂部元素統計數不小于目前元素統計數，則繼續向前疊代。

class Solution {
public:    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> nums_counts;
        for (auto &i : nums)
            ++nums_counts[i];
        
        priority_queue< pair<int,int>, vector<pair<int, int>>, greater< pair<int,int> > > pq;
        
        for (auto &p : nums_counts){
            if (pq.size()==k){
                if (pq.top().first < p.second){
                    pq.pop();
                    pq.push(make_pair(p.second, p.first));
                }
            }
            else
                pq.push(make_pair(p.second, p.first));
        }
        
        vector<int> topKF_nums(k, 0);
        while (k){
            topKF_nums[--k] = pq.top().second;
            pq.pop();
        }
            
        return topKF_nums;
    }
};