Is this bucket sort out of space???


  • 0
    M
    public static int maximumGap(int[] num) {
    	       if (num.length < 2) return 0;
    	        int maxNum = num[0];
    	        int minNum = num[0];
    	        for (int i : num) {
    	            maxNum=Math.max(maxNum,i);
    	            minNum=Math.min(minNum,i);
    	        }
    	        int len = maxNum - minNum+ 1;
    	        int[] buckets=new int[len];
    	        Arrays.fill(buckets, -1);
    	        for (int x : num) {
    	            int i = x - minNum;
    	            buckets[i]=x;
    	        }
    	        int gap = 0;
    	        int prev = 0;
    	        for (int i = 1; i < buckets.length; i++) {
    	            if (buckets[i]<0) continue;
    	            gap = Math.max(gap, buckets[i] - buckets[prev]);
    	            prev = i;
    	        }
    	        return gap;
    	    }

  • 0
    D

    You can take a look at Use Average Gap to achieve O(n) run time (Java Solution)

    Below is a solution using radix sort in java: (However, please suggest a better result.

    public class MaximumGap {
    
        public int maximumGap(int[] num) {
            if(num.length < 2) return 0;
            
            ListNode head = new ListNode(0);
            ListNode current = head;
            for(int i = 0 ; i<num.length; i++){
                current.next = new ListNode(num[i]);
                current = current.next;
            }
            
            int NoBuckets = 10;
            ListNode [] buckets;;
            ListNode [] bucketTails;
            
            boolean allZero = false;
            
            long n = 1;
            while(true){
                allZero = true;
                bucketTails = new ListNode[NoBuckets];
                buckets = new ListNode[NoBuckets];
                
                current = head.next;
                int i; int j;
                while(current!=null){
                    i = (int) (current.val / n) % 10;
                    if(current.val >= n) allZero = false;
                    
                    if(buckets[i] == null) {
                        buckets[i] = new ListNode(current.val);
                        bucketTails[i] = buckets[i];
                    }else{
                        bucketTails[i].next = new ListNode(current.val);
                        bucketTails[i] = bucketTails[i].next;
                    }
                    current = current.next;
                }
                head.next = merge(buckets);
                if(allZero) break;
                n = n*10;
            }
            current = head.next;
            int max = current.next.val - current.val; current = current.next;
            while(current.next != null){
                if(max < current.next.val - current.val) max = current.next.val - current.val;
                current = current.next;
            }
            return max;
        }
        
        public ListNode merge(ListNode[] buckets){
            ListNode dummyHead = new ListNode(0);
            ListNode current = dummyHead;
            for(int i = 0; i < buckets.length; i++){
                ListNode currentB = buckets[i];
                while(currentB != null){
                    current.next = currentB;
                    current = current.next;
                    currentB = currentB.next;
                }
            }
            return dummyHead.next;
        }
        
        class ListNode {
            int val;
            ListNode next;
            ListNode(int x){ val = x; }
        }
    
    }
    

Log in to reply
 

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