My O(n) solution


  • 2
    A

    Here are the steps of my solution:

    1-Calculate the frequency of each number using hashmap. O(N)

    2-For each frequency value, store the numbers with this frequency O(N).

    3-Loop from frequency n to 1 and take the first K numbers. O(N+K)

    The total complexity is O(N+K) which is O(N).

    My code :

    class Solution { public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int,int> freq;
            unordered_map<int,vector<int>> m;
            for(int i=0;i<nums.size();i++)
            {
                freq[nums[i]]++;
            }
            for(auto itr=freq.begin();itr!=freq.end();itr++)
            {
                m[itr->second].push_back(itr->first);
            }
            
            vector <int> res;
            for(int i=nums.size();i>=1 && k;i--)
            {
                if(!m.count(i)) continue;
                for(int j=0;j<m[i].size()&&k;j++)
                {
                    res.push_back(m[i][j]);
                    k--;
                }
            }
            return res;
        } };

  • -1
    O
    This post is deleted!

  • 0
    O
    This post is deleted!

  • 1

    @Oleksii-Danylevskyi It's pretty obvious and nothing unusual. In the whole run, the total number of inner loop iterations is at most k. Either look at how k is handled, or realize that each iteration pushes one number into the result and that the result ends up with at most k numbers.


  • 0
    O

    @StefanPochmann Agree;)


Log in to reply
 

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