C++ counting sort (intuitive solution) for O(n) time o(1) space.


  • 0
    F

    Haven't seen it done like this on forums yet.

    Basic idea:
    1.) use vector like a map and map vector index to number of times that number is seen i.e. if 5 is not seen index 5 contains value 0
    2.) if value inside index is 0 it wasn't seen before so place it in the front of array
    3.) resize to that size

    vector<int> findDisappearedNumbers(vector<int>& nums){
           vector <int> summer(nums.size()+1,0);
           for(int n: nums) summer[n]++;            
        
           int count = 0;
    
           for(int i = 1; i < summer.size(); i++)
               if(summer[i]==0) 
                   summer[count++] = i;
    
           summer.resize(count);
        
           return summer;
    }

Log in to reply
 

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