Java solution with TreeSet


  • 7
    B

    A TreeSet with size less than k is used here. So the time should be O(n * log(k)).

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || k < 0 || t < 0)
            return false;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (i - k - 1 >= 0)
                set.remove(nums[i - k - 1]);
            int n = nums[i];
            if (set.floor(n) != null && n <= t + set.floor(n) || 
                    set.ceiling(n) != null && set.ceiling(n) <= t + n)
                return true;
            set.add(n);
        }
        return false;
    }

  • 0
    S
    This post is deleted!

  • 0
    A

    I wander if the code works for following case:
    nums = [2147483646, 2147483647]; k = 1; t = 5

    when i = 1

    n = num[1] = 2147483647

    t + set.floor(n) over flow


  • 0
    L

    you need to set to long to avoid overflow


  • 0
    S

    Cool solution!
    But
    why
    if(i - k - 1 >= 0) set.remove(nums[i - k - 1]);

    Could you help me understand it please?


  • 0
    O

    @steve.j.sun If the length (size) of TreeSet >= k + 1, remove the first one.


  • 0
    S
    set.remove(nums[i - k - 1]);
    

    Does the should the set should be multi_set ?
    in some case we may remove the same num in the the k - 1 numbers before the nums[i].
    Or is there any description said all nums were different?


Log in to reply
 

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