C++ O(n+klogn) solution


  • 0
    A

    Not as good as bucket sort solution, but O(n+klogn) should be better than O(n+nlogk) when n > k > 1, right?
    Besides, this gives you sorted output.

    20 / 20 test cases passed
    Status: Accepted
    Runtime: 29 ms
    Beats 98.40%

    class Solution {
    public:
        static bool cmp(pair<int, uint>& a, pair<int, uint>& b) {return a.second < b.second;}
        vector<int> topKFrequent(vector<int>& nums, int k) {
            vector<int> res(k);
            unordered_map<int, uint> map;
            map.reserve(nums.size());
            for (int n : nums) map[n]++;
            vector<pair<int, uint>> v(map.begin(), map.end());
            make_heap(v.begin(), v.end(), cmp);
            auto iter = v.end();
            for (uint i = 0; i < k; i++) {
                pop_heap(v.begin(), iter--, cmp);
                res[i] = (*iter).first;
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.