Python without dictionary

  • 12
    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

    intuitively solution, nice~

  • 1

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

  • 0

    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

    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.