Short Java Radix sort solution on binary bits


  • 0
    C
    public class Solution {
        public int maximumGap(int[] nums) {
            int N = nums.length;
            if (N<=1) return 0;
            
            radix_sort(nums, 0, N, 31);
            
            int max_gap = 0;
            for (int i=0; i<N-1; i++)
                max_gap = Math.max(max_gap, nums[i+1]-nums[i]);
            return max_gap;
        }
        
        public void radix_sort(int[] nums, int start, int end, int d) {
            if (d<0 || start>=end) return;
            int N = nums.length;
            int l = start;
            for (int i=start; i<end; i++) 
                if( ((nums[i]>>d)&1)==0 ) swap(nums, i, l++);
            
            radix_sort(nums, start, l, d-1);
            radix_sort(nums, l, end, d-1);
        }
        
        public void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    

Log in to reply
 

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