C++ solution with explanation [bucket sort]


  • 0
    H
    class Solution {
    public:
        int maximumGap(vector<int>& nums) {
            if(nums.size()==0 || nums.size()==1)  //corner check
                  return 0;         
            int numsMin = nums[0];
            int numsMax = nums[0];
    
          //get the max value and the min value of the  array
            for(int i=1; i<nums.size(); i++)            
            {
                numsMin = min(numsMin, nums[i]);
                numsMax = max(numsMax, nums[i]);
            }
            
         // if all numbers of the array are equal, return 0 
            if(numsMin == numsMax)                  
                 return 0;
            int len = nums.size();
            int gap = ceil((numsMax-numsMin)*1.0/(len-1));
    
           // store the min value in that bucket
           // store the max value in that bucket
            vector<int> bucketMin(len, INT_MAX);         
            vector<int> bucketMax(len, INT_MIN);            
            
            for(int i=0; i<len; i++)         //scan the array
            {
                int idx = (nums[i]-numsMin)/gap;
                bucketMin[idx] = min(nums[i], bucketMin[idx]);
                bucketMax[idx] = max(nums[i], bucketMax[idx]);
            }
            
            for(int i=0; i<len; i++)
            {
                 //judge if the bucket is empty
                if(bucketMin[i] != INT_MAX)                 
                {
                    //update the max gap
                    gap = max(bucketMin[i]-numsMin, gap);      
                    numsMin = bucketMax[i];
                }
            }
            
            return gap;
        }
    };

  • 0
    Z

    your answer doesn't meet O(n) space overhead.


  • 0
    M

    Excellent solution!


  • 0
    M

    @zjs342.com Yes, it is O(n).


Log in to reply
 

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