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

For example,

Given [1,1,1,2,2,3] and k = 2, return [1,2].

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.

//O(N) Bucket Sort 
// Bucket[count number] -> number
// From last bucket (count number is the most) to first, 
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counts;
        for (const auto& i : nums) {
            ++counts[i];
        }
        vector<vector<int>> buckets(nums.size() + 1);
        for (auto kvp : counts) {
            buckets[kvp.second].push_back(kvp.first);
        }

        vector<int> result;
        cout<<buckets.size()<<endl;
        for (int i = buckets.size() - 1; i >= 0; i--) {
            cout<<"i="<<i<<endl;
            for (int j = 0; j < buckets[i].size(); j++){
                cout<<i<<j<<endl;
                cout<<buckets[i][j]<<endl;
                result.push_back(buckets[i][j]);
                if (result.size() == k) {
                    return result;
                }
            }
        }
        return result;
    }
};

//O(NLOGk) 
//map and min heap 
class Solution {
public:

    struct bigger{
        bool operator()(pair<int, int> &one, pair<int, int>two){
            return one.second > two.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> result;
        unordered_map<int, int> mapA;
        priority_queue<pair<int, int>, vector<pair<int, int>>, bigger> frequent_heap;
        for (int num : nums) {
            mapA[num]++;
        }
        //we need min heap for nlogk
        for (auto it = mapA.begin(); it != mapA.end(); it++) {
            if(frequent_heap.size() < k){
                frequent_heap.push(*it);
            } else if (it->second >= frequent_heap.top().second) {
                frequent_heap.pop();
                frequent_heap.push(*it);
            }
        }
        while (!frequent_heap.empty() ){
            auto cur = frequent_heap.top();
            frequent_heap.pop();
                        result.push_back(cur.first);

        }
        return result;
    }
};