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

  • 0

    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++)
                   summer[count++] = i;
           return summer;

Log in to reply

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