Python code by approximation.


  • 0
    R

    The ideal is simple, since we have solved the problem that contains the exact same duplicate (Contains Duplicate II), so I try to use the same code with little modification.
    Recall "the absolute difference between nums[i] and nums[j] is at most t", in fact means the number are approximately same within t. For example, we know 3.5 are "same" as 3.0, 4.4, 2.6 within t = 0.9. This is same concept as how bucket sort. Just a different way of looking at this problem.

    One way to do is we reduce the accuracy of the array number, so they are appears to be the same.

    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if k < 1 or t < 0:
            return False
      
        maps  = {}
        for i in range(len(nums)):
            keys = nums[i]/(t+1)
            for ky in (keys, keys+1, keys-1):
                if ky in maps and i-maps[ky][0] <= k and abs(nums[i] - maps[ky][1]) <= t:
                    return True
            maps[keys] = (i, nums[i])
            
            
      
        return False
    

    My previous code is:

        def containsNearbyAlmostDuplicate(self, nums, k, t):
            """
            :type nums: List[int]
            :type k: int
            :type t: int
            :rtype: bool
            """
            if k < 1 or t < 0:
                return False
            maps  = {}
            for i in range(len(nums)):
                if nums[i] in maps and i-maps[nums[i]] <= k:
                    return True
                maps[nums[i]] = i
                
            return False
    

    You can see that we only need to store additional information for integer. I think there may be more way to optimize it, if we think number difference within t as a requirement for accuracy (like 3.5 = 3.0) and should be easy.


Log in to reply
 

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