Concise AC java: standard buckets


  • 3
    I

    I believe it's the simplest approach to distributed also min/max. It simplifies also last loop. Regards.

    public class Solution {
      private class Pair {
        int min, max;
        public Pair(int min, int max) {
            this.min = min; this.max = max;
        }
      }
      public int maximumGap(int[] num) {
        if (num == null || num.length < 2) {
            return 0;
        }
        int min=num[0], max=num[0], N=num.length;
        for (int n: num) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
        if (max == min) return 0;
        int dist=(((max-min)-1)/(N-1))+1;
        Pair[] buckets = new Pair[N];
        for(int n: num) {
            int bucket = (n-min)/dist;
            Pair p = buckets[bucket];
            if (p == null) {
                buckets[bucket] = new Pair(n, n);
            } else {
                p.min = Math.min(p.min, n);
                p.max = Math.max(p.max, n);
            }
        }
        max = dist;
        int prevBucketMax=buckets[0].max;
        for (int i=1; i<buckets.length; i++) {
            if (buckets[i] == null) continue;
            max = Math.max(max, buckets[i].min-prevBucketMax);
            prevBucketMax = buckets[i].max;
        }
        return max;
      }
    }

  • 0
    D

    Another way to implement it (also in java), but the idea of using bucket sort is the same. Since this problem assumes all integers are non-negative, the below code pass. If it includes negative numbers, there is a way to solve it. Anyone can see?

    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; }
        }
    
    }

  • 0
    A

    How about input with all equal elements? Such as

    int[] num = {5,5,5,5};

    This implementation returns 1, whereas max gap is 0.


  • 0
    I

    true! thanks! :)


  • 0
    B

    I think this is not linear space because you created N new objects of Pair.


Log in to reply
 

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