Easy and clear java solution using TreeSet


  • 4
    J
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    		if (nums.length <= 0 || k <= 0) {
    			return false;
    		}
    		TreeSet<Integer> set = new TreeSet<>();
    		for (int i = 0; i < nums.length; i++) {
    			int val = nums[i];
    			/*
    			 * Returns the greatest element in this set less than or equal to
    			 * the given element, or null if there is no such element. Specified
    			 * by: floor(...) in NavigableSet Parameters: e the value to match
    			 * Returns: the greatest element less than or equal to e, or null if
    			 * there is no such element
    			 */
    			if (set.floor(val) != null && (set.floor(val) + t) >= val)
    				return true;
    			/*
    			 * Returns the least element in this set greater than or equal to
    			 * the given element, or null if there is no such element. Specified
    			 * by: ceiling(...) in NavigableSet Parameters: e the value to match
    			 * Returns: the least element greater than or equal to e, or null if
    			 * there is no such element
    			 */
    			if (set.ceiling(val) != null && (set.ceiling(val) - t) <= val)
    				return true;
    			set.add(val);
    			if (i >= k)
    				set.remove(nums[i - k]);
    		}
    		return false;
    	}

  • 0
    C

    can you pass this case?
    [1,2147483647]
    1
    2147483647


  • 0
    X
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k == 0 || nums.length <= 1) return false;
        TreeSet<Integer> kSet = new TreeSet<>((i1, i2)->{
                long diff = (long) i1 - i2;
                if (Math.abs(diff) <= t) return 0;
                else return diff > 0 ? +1 : -1;
            });
    
        for (int i = 0; i < nums.length; ++i) {
            if (!kSet.add(nums[i])) return true;
            if(i>=k)kSet.remove(nums[i - k]);
        }
        return false;      
    }

Log in to reply
 

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