java radix sort


  • 3

    Because the question has tell us that every number has 32 bits. This can remind us to use radix sort whose run time and extra space are both linear.

    public class Solution {
        public int maximumGap(int[] nums) {
            if(nums == null || nums.length == 0 || nums.length == 1) {
                return 0;
            }
            int res = 0;
            radixsort(nums);
            for(int i = 1 ; i < nums.length ; i++) {
                res = Math.max(res , nums[i] - nums[i-1]);
            }
            return res;
        }
        
        protected void radixsort(int[] nums) {
            int[] temp = new int[nums.length];
            for(int i = 0 ; i < 32 ; i++) {
                int[] c = new int[2];
                for(int num : nums) {
                    int digit = num >> i;
                    if((digit & 1) == 0) c[0]++;
                    else c[1]++;
                }
                c[1] = c[0] + c[1];
                for(int j = nums.length-1 ; j >= 0 ; j--) {
                    int digit = (nums[j] >> i) & 1;
                    temp[c[digit]-1] = nums[j];
                    c[digit]--;
                }
                for(int j = 0 ; j < nums.length ; j++) {
                    nums[j] = temp[j];
                }
            }
        }
    }

Log in to reply
 

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