LeetCode #347 前 K 個高頻元素

347. 前 K 個高頻元素

給你一個整數數組 

nums

 和一個整數 

k

 ，請你傳回其中出現頻率前 

k

 高的元素。你可以按 任意順序傳回答案。

示例 1:

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

示例 2:

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

提示：

• 1 <= nums.length <= 105

• k

   的取值範圍是 

  [1, 數組中不相同的元素的個數]

• 題目資料保證答案唯一，換句話說，數組中前 

  k

   個高頻元素的集合是唯一的

進階：你所設計算法的時間複雜度 必須 優于 

O(n log n)

 ，其中 

n

 是數組大小。

class Solution {
public:
    map<int,int> ma;
    typedef pair<int,int> P;
    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(int i = 0;i < nums.size();i++) ma[nums[i]]++;
        priority_queue<P > que;
        map<int,int>::iterator it;
        for(it = ma.begin();it != ma.end();it++){
            que.push({it->second,it->first});
        }
        vector<int> out;
        for(int i = 0;i < k;i++){
            out.push_back(que.top().second);
            que.pop();
        }
        return out;
    }
};