3 ways to solve this problem


  • 44
    R

    using heap

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
            unordered_map<int, int> cnt;
            for (auto num : nums) cnt[num]++;
            for (auto kv : cnt) {
                pq.push({kv.second, kv.first});
                while (pq.size() > k) pq.pop();
            }
            vector<int> res;
            while (!pq.empty()) {
                res.push_back(pq.top().second);
                pq.pop();
            }
            return res;
        }
    };
    

    using selection algorithm

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            vector<int> res;
            if (!nums.size()) return res;
            unordered_map<int, int> cnt;
            for (auto num : nums) cnt[num]++;
            vector<pair<int, int>> num_with_cnt;
            for (auto kv : cnt) {
                num_with_cnt.push_back({kv.first, kv.second});
            }
            kselection(num_with_cnt, 0, num_with_cnt.size()-1, k);
            for (int i = 0; i < k && i < num_with_cnt.size(); ++i) {
                res.push_back(num_with_cnt[i].first);
            }
            return res;
        }
    
        void kselection(vector<pair<int, int>>& data, int start, int end, int k) {
    
            if (start >= end) return;
            auto pv = data[end];
            int i = start;
            int j = start;
            while (i < end) {
                if (data[i].second > pv.second) {
                    swap(data[i++], data[j++]);
                } else {
                    ++i;
                }
            }
            swap(data[j], data[end]);
            int num = j - start + 1;
            if (num == k) return;
            else if (num < k) {
                kselection(data, j + 1, end, k - num);
            } else {
                kselection(data, start, j - 1, k);
            }
        }
    };
    

    using bucket sort

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            vector<int> res;
            if (!nums.size()) return res;
            unordered_map<int, int> cnt;
            for (auto num : nums) cnt[num]++;
            vector<vector<int>> bucket(nums.size() + 1);
            for (auto kv : cnt) {
                bucket[kv.second].push_back(kv.first);
            }
    
            for (int i = bucket.size() - 1; i >= 0; --i) {
                for (int j = 0; j < bucket[i].size(); ++j){
                    res.push_back(bucket[i][j]);
                    if (res.size() == k) return res;
                }
            }
    
            return res;
        }
    };

  • 0
    L

    { 1st will run in n * log(n) for input like [1, 2, ..., n] } my bad - you're keeping the queue at size k

    2nd - since pivot is always last element - can run in n^2 in worst case

    3rd is neat


  • 0
    H

    another better bucket sort way

    class Solution {
    public:
         vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int,int> mp;
            vector<int> ans;
            int max_frequence = 0,last;
            for(auto x:nums)
                 max_frequence = max(++mp[x],max_frequence);
             vector<int> frequence(max_frequence + 1);
            for(auto x:mp)
                frequence[x.second]++;
            for(int i = max_frequence; k > 0; i--)
                 k -= frequence[last=i];
            for(auto x:mp)
                if(x.second >last ||(x.second == last && ++k > 0))
                    ans.push_back(x.first);
            return ans;
         }
    };

  • 0
    S

    Thank you for the nice solutions. But I think the first and the second would be O(nlogn).


  • 0
    S

    actually I think we don't need that part "&& ++k > 0" inside this if statement:

    if(x.second >last ||(x.second == last && ++k > 0))

    what's the reason for that?


  • 0
    H

    for corner case like [1,1,2,2,3,3] 2


  • 0
    S

    interestingly after removing "&& ++k > 0", still got AC from OJ


  • 0
    H

    -_-|| ,The test cases are weak....


  • 0
    A

    @robin8 What is the running time and space complexity for the bucket sort solution i.e. the 3rd one?


  • 1
    D

    It looks like kselection can be impemened using std::nth_element:

    auto byCount = [](const pair<int,int>& a, const pair<int,int>&b) { return a.second > b.second; };
    nth_element(num_with_cnt.begin(), num_with_cnt.begin()+k, num_with_cnt.end(), byCount);
    

  • -1
    N

    @sculd I think the first solution is O(n logk).
    step 1 counting using unordered_map takes O(n).
    step 2 partial sorting using priority_queue takes O(n log k);
    step 3 transforming into a sorted vector takes O(k).
    so, overall it is O(n logk).

    Additionally, I think there's problem with step 3.
    Popped element should be put into vector res in a reversed order instead of that in the written code, or else the most frequent element will be the last one in the vector res.


  • 0
    F
    This post is deleted!

  • 0
    G

    厉害了
    厉害了
    厉害了
    厉害了
    厉害了


  • 0
    C

    The time complextiy of your kselect function is O(logn) or O(logk)?


  • 0

    The code is quite clear and beautiful.
    But maybe the calling of recursion part in selection algorithm :

     if (num == k) return;
             else if (num < k) {
                 kselection(data, j + 1, end, k - num);
             } else {
                 kselection(data, start, j - 1, k);
             }
    

    can be written in

    if(k == j)return;
    if(k > j)kselection(data, j + 1, end, k);
      else kselection(data, start, j - 1, k);
    

    which looks a little bit cleaner.


  • 0

    Does the result from the second solution keep the order of the frequency?


Log in to reply
 

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