A simple stupid c++ O(n) solution with an unordered_map and a vector


  • 1
    S
    class Solution {
     public:
    	 vector<int> topKFrequent(vector<int>& nums, int k) {
    		 unordered_map<int, int> imap;
    	
    		 vector<int> count(nums.size() + 1, 0);
    		 int min_times = 0;
    		 
    		 for (auto &e : nums) {
    			int times =  ++imap[e];
    			++count[times];
    		 }
    
    		 for (min_times = count.size() - 1; min_times > 0 && count[min_times] < k ; --min_times) {}
    
    		 int i = 0;
    		 
    		 for (auto &e : imap) {
    			 if (e.second > min_times) {
    				 count[i ++] = e.first;
    			 }
    		 }
    		 for (auto &e : imap) {
    			 if (e.second == min_times) {
    				 count[i ++] = e.first;
    			 }
    		 }
    		 return vector<int>(count.begin(), count.begin() + k);
    
    	 }
     };

  • 0
    N

    The result wont be sorted, e.g for this input [6,6,1,6,6,6,1,1,2,9,9]
    3
    u will get [1,6,9] instead of [6, 1, 9]


  • 0

    iteration in a unordered_map will never reach restricted O(n). In the worst case, it is as large as O(n^2).


Log in to reply
 

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