Python without dictionary


  • 12
    L
    class Solution:
        # @param {integer[]} nums
        # @param {integer} k
        # @param {integer} t
        # @return {boolean}
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            ind = sorted(range(len(nums)), key = lambda x: nums[x])
            for i in range(len(nums)-1):
                j = i + 1
                while j < len(nums) and nums[ind[j]] - nums[ind[i]] <= t:
                    if abs(ind[i]-ind[j]) <= k:
                        return True
                    j += 1
            return False
    

    ind is an array of the indexes of sorted num. Iterate through ind to check if nums are within t and ind are within k.


  • 0
    O

    intuitively solution, nice~


  • 1
    L

    This algorithm's time complexity seems to be O(n^2), why it didn't cause time limit exceed in OJ?


  • 0
    C

    I think the time complexity of this method is not O(n^2). It should be O(n*t), as the while loop will have t comparisons at most. The brutal-force solution which searches each k-sized bucket is O(n*k^k). So it depends on the values of t and k^k when comparing which one is better.


  • 0
    L

    Yes you are right, later I figured it out. Since it's called Contain Duplicate III, the t should be a relatively small number :)


  • 0

    @caikehe I thought it should be O(n*t) vs O(n*k), because in these family of solutions position / k and num / t are interchangeable.


Log in to reply
 

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