Share my LSD solution


  • 1
    X

    Simple and scale well for huge input

    public class Solution {
    public int maximumGap(int[] nums) {
    	if (nums.length < 2) return 0;
    	int R = 2;
    	int N = 32;
    
    	for (int i = 0; i < N; i++) {
    		int[] count = new int[R + 1];
    		int[] aux = new int[nums.length];
    
    		for (int v : nums) 
    			count[((v >>> i) & 1) + 1]++;
    
    		for (int r = 0; r < R; r++)
    			count[r + 1] += count[r];
    
    		for (int v : nums)
    			aux[count[(v >>> i) & 1]++] = v;
    
    		for (int j = 0; j < nums.length; j++)
    			nums[j] = aux[j];
    	}
    
    	int res = Integer.MIN_VALUE;
    	for (int i = 1; i < nums.length; i++) 
    	    res = Math.max(nums[i] - nums[i -1], res);
    	
    	return res;    
    }
    

    }


Log in to reply
 

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