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.

Analysis

标准radix sort，熟悉该算法，linear time complexity

Code

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums==null || nums.length < 2) return 0;

        //find the maximum number in nums to determine the longest digits to deal with in the following steps
        int m = nums[0];
        for (int num:nums){ if(num>m) m=num;}

        int exp=1; //1,10,100,1000
        int R =10; //10 digits

        //put the sorted array here
        int[] aux = new int[nums.length];

        while (m/exp>0){ // go through all digits
            int[] count = new int[R];

            for (int i=0; i<nums.length; i++){
                count[(nums[i]/exp)%10]++;
            }

            for (int i=1; i<count.length; i++){
                count[i]+=count[i-1];
            }

            for(int i=nums.length-1; i>=0;i--){
                aux[--count[(nums[i]/exp)%10]] = nums[i];
            }

            for(int i=0; i<nums.length; i++){
                nums[i]=aux[i];
            }
            exp*=10;
        }

        //find the maximum gap from sorted array aux
        int max=0;
        for (int i=1; i<aux.length; i++){
            max = Math.max(max, aux[i]-aux[i-1]);
        }

        return max;
    }
}

Reference