Day 98, ##, Maximum Gap

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
------------------------------------------------------------------------------
reference 
use n - 1 buckets
注意 bucketSize用double

class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size() < 2) return 0;
        int min_val = num[0];
        int max_val = num[0];
        for (int i = 1; i < num.size(); i++) {
            min_val = min(num[i],min_val);
            max_val = max(num[i],max_val);
        }
        
        double bucketSize = (max_val - min_val) * 1.0 / (num.size() - 1);
        vector<int> maxBucket(num.size() - 1, -1);
        vector<int> minBucket(num.size() - 1, INT_MAX);
        for (int i = 0; i < num.size(); i++) {
            if (num[i] == min_val || num[i] == max_val) continue;
            int bucket = (int)((num[i] - min_val) / bucketSize);
            maxBucket[bucket] = max(num[i],maxBucket[bucket]);
            minBucket[bucket] = min(num[i],minBucket[bucket]);
        }
        
        int maxGap = INT_MIN;
        int preMax = min_val;
        for (int i = 0; i < num.size() - 1; i++) {
            if (maxBucket[i] == -1) continue;
            maxGap = max(maxGap,minBucket[i] - preMax);
            preMax = maxBucket[i];
        }
        maxGap = max(maxGap,max_val - preMax);
        return maxGap;
    }
};

Update Feb-18-2015
radix sort

class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size() < 2) return 0;
        vector<int> one;
        vector<int> zero;
        
        for (int i = 0; i < 32; i++) {
            int mask = 1 << i;
            for (int j = 0; j < num.size(); j++) {
                if (num[j] & mask) {
                    one.push_back(num[j]);
                }else {
                    zero.push_back(num[j]);
                }
            }
            
            zero.insert(zero.end(),one.begin(),one.end());
            num =zero;
            one.clear();
            zero.clear();
        }
        
        int maxGap = 0;
        for (int i = 1; i < num.size(); i++) {
            maxGap = max(num[i] - num[i - 1],maxGap);
        }
        
        return maxGap;
    }
};

if (num[j] & mask) 判断的是0或者是非0，而不是1或0
radix sort, 10-base
REF

class Solution {
public:
    int getMax(vector<int> &nums) {
        int maxNum = 0;
        for (int i = 0; i < nums.size(); i++) {
            maxNum = max(nums[i],maxNum);
        }
        return maxNum;
    }

    void countSort(vector<int>& nums, int m) {
        vector<int> count(10,0);
        for (int i = 0; i < nums.size(); i++) {
            count[(nums[i] / m) % 10]++;
        }
        
        // calculate start point for each key
        int total = 0;
        for (int i = 0; i < 10; i++) {
            int oldCount = count[i];
            count[i] = total;
            total += oldCount;
        }
        
        // sort
        vector<int> rt(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            rt[count[(nums[i] / m) % 10]] = nums[i];
            count[(nums[i] / m) % 10]++;
        }
        
        nums = rt;
    }

    int maximumGap(vector<int>& nums) {
        int maxNumber = getMax(nums);
        for (int m = 1; m <= maxNumber; m *= 10) {
            countSort(nums,m);
        }
        
        int maxGap = 0;
        for (int i = 1; i < nums.size(); i++) {
            maxGap = max(maxGap,nums[i] - nums[i - 1]);
        }
        
        return maxGap;
    }
};