Simple O(n) C++ solution with explanation, 18 msec, result is sorted.


  • 0
    Y

    The Algorithm: hash map + bucket sort.

    1. Use hash map to get frequencies.
    2. Use array of lists (it's more efficient than array of arrays) to sort frequencies. The size of array is not bigger than number of elements in the original array. Put the frequency into correspondent place in the new array.
    3. Output the buckets till the result array size is equal K.
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> frequencyMap;
            for(int n: nums)
                frequencyMap[n]++;
            
            vector<list<int> > buckets(nums.size(), list<int>());
            for(auto m: frequencyMap)
                buckets[nums.size()-m.second].push_back(m.first);
            
            vector<int> result;
            for(auto& bucket: buckets)
                for(int n: bucket){
                    result.push_back(n);
                    if (result.size() == k)
                        return result;
                }
            return result;
        }
    

Log in to reply
 

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