[Leetcode] Top K Frequent Elements(Medium)

發表於： 2022-04-09 分類於： leetcode

字數： 240 閱讀：≈ 1分鐘瀏覽：

LeetCode 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

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

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

How can we solve this problem?

這一題需要我們返回K個數量最多的element。所以，我們可以使用map記錄我們array中element的個數，然後在把他們以<frequency,element>存到priority queue/max queue，最後只要返回priority queue中的k個element即可。

Solution:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        unordered_map<int,int> map;
        priority_queue<pair<int,int>> q;
        for(auto i : nums) map[i]++; //counter numbers 
        for(auto it : map) q.push({it.second,it.first}); //according to the second for priority
        while(k-- > 0) {
            res.push_back(q.top().second);
            q.pop();
        }
        return res;
    }
};