Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Example 2:

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

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

=========================================================

class Solution {

public:

    struct comp {

        bool operator()(pair<int, int> first, pair<int,int> second) {

            return first.second < second.second;

        }

    };

    

    vector<int> topKFrequent(vector<int>& nums, int k) {

        map<int, int> mp;

        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;

        

        for (int num : nums) {

            mp[num]++;

        }

        

        for (auto entry : mp) {

            pq.push(make_pair(entry.first, entry.second));

        }

        

        // since k is always valid.

        vector<int> ans;

        for (int i = 0 ; i < k; i++) {

            int elem = pq.top().first;

            ans.push_back(elem);

            pq.pop();

        }

        

        return ans;

    }

};

======================== Order n space n ==========

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        vector<vector<int>> bucket(nums.size() + 1);
        vector<int> res;
        for (auto a : nums) ++m[a];
        for (auto it : m) {
            bucket[it.second].push_back(it.first);
        }
        for (int i = nums.size(); i >= 0; --i) {
            for (int j = 0; j < bucket[i].size(); ++j) {
                res.push_back(bucket[i][j]);
                if (res.size() == k) return res;
            }
        }
        return res;
    }
};