My solution based on counting sort encounter a runtime error with for [2,99999999].


  • 0
    Z
    public int maximumGap(int[] num) {  
        if(num.length <= 1) 
        	return 0;
        num = countingSort(num);
        int maxDiff = num[1] - num[0];
        for(int i=2;i<num.length;++i) {
        	int temp = num[i] - num[i-1];
        	if(maxDiff < temp) {
        		maxDiff = temp;
        	}
        }
        return maxDiff;
    }
    public int[] countingSort(int[] nums) {
    	int MAX = nums[0];
    	for(int i=1;i<nums.length;++i) {
    		if(MAX < nums[i])
    			MAX = nums[i];
    	}
    	int[] result = new int[nums.length];
    	int[] C = new int[MAX+1];
    	for(int j=0;j<nums.length;++j) {
    		C[nums[j]] = C[nums[j]] + 1;
    	}
    	for(int i=1;i<C.length;++i) {
    		C[i] = C[i] + C[i - 1];
    	}
    	for(int j=nums.length-1;j >= 0;--j) {
    		result[C[nums[j]] - 1] = nums[j];
    		C[nums[j]] -= 1;
    	}
    	return result;
    }

  • 0
    J

    I think you run out of memory. You should try radix sort starting form least significant 8-bit. And iteratively do 8-15th bit, 16-23rd bit, 24-31st bit. In each iteration you can use counting sort. Since counting sort is stable and you can get a sorted result without high requirement compared to your implementation since the radix number is 256 instead of potential Integer.MAX_VALUE.


Log in to reply
 

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