347 - Top K Frequent Elements

#medium

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]

priority_queue以頻率高的數字為高權重。

1. 熟悉priority_queue
2. 熟悉map的iterator的訪問

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for ( int i = 0; i < nums.size(); i++ ) {
            mp[nums[i]]++;
        }

        priority_queue<pair<int,int>> pq;
        for ( auto it = mp.begin(); it != mp.end(); it++ ) {
            // pair<first, second>: first is frequency,  second is number
            pq.push( pair( it->second, it->first ) );
        }

        vector<int> v_res;
        for ( int i = 0; i < k; i++ ) {
            v_res.push_back(pq.top().second);
            pq.pop();
        }

        return v_res;
    }
};