Average O(n) C++ Solution Using Quickselect


  • 1
    P

    Short, simple C++ solution using Quickselect that will take O(n) time on average, using std algorithm functions.

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int,int> counts;
            for (int num : nums) ++counts[num];
            vector<pair<int,int>> freqs;
            for (auto vt : counts) freqs.push_back({vt.second, vt.first});
            nth_element(freqs.begin(), freqs.end() - k, freqs.end());
            
            vector<int> out(k);
            transform(freqs.end() - k, freqs.end(), out.begin(), [](pair<int,int> vt){return vt.second;});
            return out;
        }
    };
    

Log in to reply
 

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