top-k-frequent-elements

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]

Example 2:

Input: nums = [1], k = 1 Output: [1]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        // base case
        // 如果 k == n，回傳原數列
        if(k == n) return nums;

        // {數字, 出現的頻率}
        unordered_map<int, int> freq;
        priority_queue<pair<int, int>> q;
        vector<int> res;

        // 算數字出現的頻率
        for(auto num : nums) ++freq[num];

        // 將出現頻率的推到 priority queue 排列
        // 預設是 max heap，由大排到小
        for(auto it : freq) {
            q.push({it.second, it.first});
        }

        for(int i = 0; i < k; i++) {
            // 將出現頻率前 k 的數字推到 res
            res.push_back(q.top().second); q.pop();
        }
        return res;
    }
};

• T: $O(N \cdot \log k)$
• S: $O(N + k)$