## [347\. Top K Frequent Elements](https://leetcode.com/problems/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;
    }
};

:::success
- 時間複雜度：$O(N \cdot \log k)$
- 空間複雜度：$O(N + k)$
:::