C++ hash and heap calls (no explicit priority queue)


  • 0
    M

    This uses the C++ library make_heap() and pop_heap() calls which act on a heap stored as a vector. One advantage is that the heap can be constructed in linear time -- as opposed to inserting each element into the heap individually. It's also straight forward to pop/read elements from the heap without explicitly removing them from the collection.

            vector<int> topKFrequent(vector<int>& nums, int k)
            {
                unordered_map<int, int> M;
                for (auto num : nums) M[num]++;
    
                // Create a heap from the frequency counts
                auto cmp = [](const pair<int, int>& lhs, const pair<int, int>& rhs)
                { return lhs.second < rhs.second; };
    
                vector<pair<int, int>> vals(begin(M), end(M));
                make_heap(begin(vals), end(vals), cmp);
    
                // Pop/read off the first k elements of the heap
                vector<int> res(k);
                for (int i = 0; i < k; ++i)
                {
                    pop_heap(begin(vals), end(vals) - i, cmp);
                    res[i] = (end(vals) - 1)[-i].first;
                }
    
                return res;
            }
    

Log in to reply
 

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