C++ using kth-order statistic (std::nth_element from the standard library; 19ms)


  • 0
    M

    Bucket sort may be the appropriate answer for this question, but using the kth-order statistic is great if a simple library call is available, as it is in C++. Time for nth_element() is O(n) on average.

        vector<int> topKFrequent_orig(vector<int> nums, int k) {
            // Count up frequencies
            unordered_map<int, int> freqs;
            for (auto num : nums)
                freqs[num]++;
    
            // Compare frequency counts (order = decreasing)
            auto cmp = [](pair<int, int> lhs, pair<int, int> rhs)
            { return lhs.second >rhs.second; };
    
            // Flatten out and take kth-order statistic
            vector<pair<int, int>> flat(begin(freqs), end(freqs));
            nth_element(begin(flat), begin(flat) + k, end(flat), cmp);
    
            // Copy over the results
            vector<int> res(k);
            for (int i = 0; i < k; ++i)
                res[i] = flat[i].first;
    
            return res;
        }
    

Log in to reply
 

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