Another accepted Java code


  • 0
    class Bucket {
        int min;
        int max;
        Bucket(int x, int y) {
            min = x;
            max = y;
        }
    }
    
    public int maximumGap(int[] a) {
        if (a == null || a.length < 2) {
            return 0;
        }
        
        int n = a.length;
        
        // step 1. find out the min and max in a[] and calculate the bucket length
        int min = a[0], max = a[0];
        
        for (int i = 1; i < n; i++) {
            min = Math.min(min, a[i]);
            max = Math.max(max, a[i]);
        }
        
        double len = (double)(max - min) / (double)(n - 1);
        
        // step 2. create bucket map that tracks the min & max of each bucket
        Map<Integer, Bucket> map = new TreeMap<Integer, Bucket>();
        
        for (int i = 0; i < n; i++) {
            // locate the bucket index
            int k = (int)(a[i] / len);
            
            if (map.containsKey(k)) {
                Bucket bucket = map.get(k);
                bucket.min = Math.min(bucket.min, a[i]);
                bucket.max = Math.max(bucket.max, a[i]);
            } else {
                map.put(k, new Bucket(a[i], a[i]));
            }
        }
        
        // step 3. find out the max gap
        int res = 0;
        
        Bucket prev = null;
        
        for (Map.Entry<Integer, Bucket> entry : map.entrySet()) {
        	Bucket curr = entry.getValue();
        	if (prev != null) {
        		res = Math.max(res, curr.min - prev.max);
        	}
        	prev = curr;
        }
        
        return res;
    }

  • 0
    Y

    My java similar solution:

    public int maximumGap(int[] num) {
            if(num.length<2) return 0;
            int max=num[0];
            int min=num[0];
            for(int i=1;i<num.length;i++){
                if(num[i]<min) min=num[i];
                if(num[i]>max) max=num[i];
            }
            Integer[] nmax=new Integer[num.length+1];
            Integer[] nmin=new Integer[num.length+1];
            for(int i=0;i<num.length;i++){
                int ind=(int)Math.floor((double)(num.length-1)*(num[i]-min)/(max-min));
                if(nmin[ind]==null||nmax[ind]==null){
                    nmax[ind]=num[i];
                    nmin[ind]=nmax[ind];
                }
                else{
                    if(num[i]>nmax[ind]) nmax[ind]=num[i];
                    if(num[i]<nmin[ind]) nmin[ind]=num[i];
                }
            }
            int r=Integer.MIN_VALUE;
            int p=nmax[0];
            for(int i=1;i<num.length+1;i++){
                if(nmin[i]==null||nmax[i]==null) continue;
                r=Math.max(r,nmin[i]-p);
                p=nmax[i];
            }
            return r;
        }

  • 0
    E

    Very nice! Why call Math.floor() before convert to int? I am thinking (int) would do floor anyway, any accuracy concern?


Log in to reply
 

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