Radix Sort based Java code, 5ms


  • 0
    F
    public class Solution {
        public int maximumGap(int[] nums) {
            if(nums.length < 2) {
                return 0;
            } else {
                int maxDiff, cnt;
                
                radixSort(nums);
                for(cnt = 1, maxDiff = 0; cnt < nums.length; cnt++) {
                    maxDiff = Math.max(maxDiff, nums[ cnt ]-nums[ cnt-1 ]);
                }
                return maxDiff;
            }
        }
    
        private void radixSort(int[] nums) {
            final int digits = 4;  //Valid values: 1,2,4,8,16
            final int maxDigitVal = 1 << digits;
            final int mask = maxDigitVal-1;
            int[] digitCnts = new int[ maxDigitVal ];
            int[] sortedNums = new int[ nums.length ];
    
            for(int iteration = 0; iteration < 32/digits; iteration++) {
                Arrays.fill(digitCnts, 0);
                for(int num:nums) {
                    digitCnts[ (num >> iteration*digits) & mask ]++;
                }
    
                int preCnt = digitCnts[ 0 ];
                digitCnts[ 0 ] = 0;
                for(int pos = 1; pos < maxDigitVal; pos++) {
                    int curCnt = digitCnts[ pos ];
                    digitCnts[ pos ] = preCnt+digitCnts[ pos-1 ];
                    preCnt = curCnt;
                }
    
                for(int num:nums) {
                    sortedNums[ digitCnts[ (num >> iteration*digits) & mask ]++ ] = num;
                }
    
                for(int cnt = 0; cnt < nums.length; cnt++) {
                    nums[ cnt ] = sortedNums[ cnt ];
                }
            }
        }
    }

Log in to reply
 

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