[java/6ms] Bucket sort


  • 0

    I referenced from the CPP version

    Well there's an edge case that can't be handle by the Java. If the min = Integer.MIN_VALUE, max = Integer.MAX_VALUE; and t = 1, size will still overflow, which will be 2^31 instead of 2^31-1. In short, if they add this test case, [MAX, MIN], t=1, k=ANY, the program won't work. To avoid this, you should actually handle this case separately.

    Another reason is that in Java, only int type can be used to index on an array, so the size can't be long type. array size limit. However, CPP has no hard limitation on the array size.

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (k < 1 || t < 0)
                return false;
    
            long range;
            long max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for (int num : nums) {
                max = max > num ? max : num;
                min = min < num ? min : num;
            }
            range = max - min + 1;
            long bucket_with = ((long) t) + 1;
            int size = (int) (range / bucket_with + 1);
            int[] buckets = new int[size];
            Arrays.fill(buckets, -1);
    
            for (int i = 0; i < nums.length; i++) {
                int bucket_idx = (int) ((((long) nums[i]) - min + 1) / bucket_with );
                if (buckets[bucket_idx] >= 0) {
                    return true;
                }
                buckets[bucket_idx] = i;
                
                if (bucket_idx > 0) {
                    int j = buckets[bucket_idx-1];
                    if (j >= 0 && Math.abs(((long) nums[i]) - nums[j]) <= t) {
                        return true;
                    }
                }
                
                if (bucket_idx < size-1) {
                    int j = buckets[bucket_idx + 1];
                    if (j >= 0 && Math.abs(((long) nums[i]) - nums[j]) <= t) {
                        return true;
                    }
                }
                
                if (i >= k) {
                    buckets[(int) ((((long) nums[i-k]) - min + 1) / bucket_with )] = -1;
                }
            }
            
            return false;
        }
    

Log in to reply
 

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