Contains Duplicate III

题目描述

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

解题方法

从index的difference最多为k我们可以感觉有点像sliding window, 在Move的过程中增加和减少element, 而如果对于每一个value, 都要将[value-t, value + t]这个范围找一遍的话，肯定时间复杂度太高。

利用Bucket sort的思想

如果需要在一定等间隔范围的查找，可以利用bucket sort的思想减小查找比较的范围

如果： | nums[i] - nums[j] | <= t   式a

等价： | nums[i] / t - nums[j] / t | <= 1   式b

推出： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1   式c

​等价： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 式d

那么对于每一个Num,只要

key = num / t

然后搜寻(key-1, key, key + 1)是否在维护的最大size为k的map中，并且判断真实的value diff是否<= t就可以了。

快速delete开头的key/value pair

在sliding window总我们用hashheap, 在Python中有OrderedDict这个数据结构，可以用在这里

OrderedDict.popitem(last=True)
The popitem() method for ordered dictionaries returns and removes a (key, value) pair. 
The pairs are returned in LIFO order if last is true or FIFO order if false.

Solution

from collections import OrderedDict

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if not nums:
            return False
        if t < 0 or k < 1:
            return False
        window = OrderedDict()
        for idx, num in enumerate(nums):
            # bucket size should be at least 1
            key = num / max(1, t)
            for i in (key, key-1, key+1):
                if i in window and abs(window[i] - num) <= t:
                    return True
            window[key] = num
            if idx >= k:
                window.popitem(last=False)

        return False

Reference