Without Using Long to avoid overflow, 7ms java solution (buckets sort)


  • 0
    public class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if(nums.length == 0) return false;
            if(k ==0 || t<0) return false;
            int max = nums[0], min = nums[0];
            for(int i=1; i<nums.length; i++){
                max = Math.max(max, nums[i]);
                min = Math.min(min, nums[i]);
            }
            if(max == min) return t == 0;
            int gap = Math.max(t,1);
            int numBuckets = (int)Math.ceil(((double)max-min)/gap)+1;
            int[] buckets = new int[numBuckets];
            boolean[] used = new boolean[numBuckets];
            for(int i=0; i<nums.length; i++){
                int ind = nums[i]/gap-min/gap+( (nums[i]%gap) - (min%gap))/gap;
                if(used[ind]) return true;
                used[ind] = true;
                buckets[ind] = nums[i];
                if(ind+1<numBuckets && used[ind+1] && buckets[ind+1]-t<=buckets[ind]) return true;
                if(ind-1>=0 && used[ind-1] && buckets[ind]-t<=buckets[ind-1]) return true;
                if(i>=k){
                   ind = nums[i-k]/gap-min/gap+( (nums[i-k]%gap) - (min%gap))/gap;
                   used[ind] = false;
                }
            }
            return false;
            
        }
    }

  • 0
    A

    Hi, would you please give some detail explanation? thx.


Log in to reply
 

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