O(n) in Java using bucket


  • 0
    T

    The bucket idea comes from https://discuss.leetcode.com/topic/15199/ac-o-n-solution-in-java-using-buckets-with-explanation.
    Basically, just use bucket = nums[i]/t as key of the hashmap to solve Contains Duplicate II.
    So you only need to check bucket, bucket - 1, bucket + 1 for possible number in range t of current number.

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if(t < 0 || k < 1)
                return false;
    	HashMap<Long, Integer> map = new HashMap<Long, Integer>();
    	long bucket = 0;
    	int j = t;
    	if(t == 0)
    	    j = 1;
    	for(int i = 0; i < nums.length; i++){
    		bucket = ((long)nums[i])/j;
    		if(map.containsKey(bucket) &&
    				Math.abs(nums[map.get(bucket)] - nums[i]) <= t){
    			if(i - map.get(bucket) <= k)
    				return true;
    		}
    		if(map.containsKey(bucket - 1) &&
    				Math.abs((long)nums[map.get(bucket- 1)] - nums[i]) <= t){
    			if(i - map.get(bucket - 1) <= k)
    				return true;
    		}
    		if(map.containsKey(bucket + 1) &&
    				Math.abs((long)nums[map.get(bucket + 1)] - nums[i]) <= t){
    			if(i - map.get(bucket + 1) <= k)
    				return true;
    		}
    		map.put(bucket, i);
    		
    	}
    	return false;
    }
    

  • 0
    C
    This post is deleted!

Log in to reply
 

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