C++ Bucket sort with explanation and clear figure


  • 0
    G

    /*
    Bucket sort

    Given the MIN and MAX of the array, the gap between MIN and MAX is MAX-MIN, there are n-1 intervals, so the largest
    interval length, denoted as maxGap, must be larger than ceiling[(MAX-MIN)/(n-1)]
    
    We construct several buckets with length maxGap, each one is close to another. e.g. [5,1,3,2,4,10]
    
    Bucket 
       0   1    2    3
    |____|____|____|___|
    1   3|4  6|7  9|10
    
    we put the numbers into its corresponding bucket
    
    Min 1 2   4         10
    Max     3   5       10
        |____|____|____|___|
        1   3|4  6|7  9|10
    
    
    to count the maximum different, we can ignore the difference of numbers in the same busket, because they are definitely
    smaller than maxGap
    
    ***Remark, there are at most n groups, for example, 1, 3, 10, we can get 1-3, 4-6, 7-9 with length 3, and 10
    

    */

    class Solution {
    public:
        int maximumGap(vector<int>& nums) {
            int n = nums.size();
            if (n < 2) return 0;
            if (n == 2) return abs(nums[0] - nums[1]);
            vector<int> bucketMin(n, INT_MAX), bucketMax(n, INT_MIN), bucket_cnt(n, 0);
            int maxV = INT_MIN, minV = INT_MAX;
            for (auto c: nums) {
                maxV = max(c, maxV);
                minV = min(c, minV);
            }
            if (maxV - minV == 0) return 0;
            int maxGap = (maxV - minV) / (n - 1);
            maxGap = maxGap * (n - 1) == (maxV - minV)? maxGap: (maxGap + 1);
            for (auto c: nums) {
                int bucket_id = (c - minV) / maxGap;
                bucket_cnt[bucket_id]++;
                bucketMax[bucket_id] = max(bucketMax[bucket_id], c);
                bucketMin[bucket_id] = min(bucketMin[bucket_id], c);
            }
            int maxDistance = INT_MIN;
            int lastMax = bucketMin[0];
            for (int i = 0; i < n; i++) {
                if (bucket_cnt[i] == 0) continue;
                maxDistance = max(maxDistance, bucketMin[i] - lastMax);
                lastMax = bucketMax[i];
            }
            return maxDistance;
        }
    };
    

Log in to reply
 

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