分享一个本题的python解决思路

Question

def containsNearbyAlmostDuplicate(self, nums, k, t):
        if k < 1:
            return False
        dic = collections.OrderedDict()
        for n in nums:
            key = n if not t else n // t
            for m in (dic.get(key - 1), dic.get(key), dic.get(key + 1)):
                if m is not None and abs(n - m) <= t:
                    return True
            if len(dic) == k:
                dic.popitem(False)
            dic[key] = n
        return False

由于python内置的OrderedDict虽然底层实现是二分搜索树，但是不提供floor&ceil操作

而且第三方库bintrees是没法在LeetCode里调用的

所以只能换一种写法了，使用n//t将区间[n-t,n+t]缩减为[n//t-1,n//t+1]

具体思路是，将整个数组分成一个个区间，每个区间的长度是t。这样一来，只要"n所在的区间、n所在的区间的前后两个区间"这三个区间中，有一个数，并且这个数满足abs(n-m)<=t，就找到了一个m。

Answer 1

liuyubobobo 2018-02-08 07:41:15

大赞！感谢分享：）

Answer 2

提问者 ShiveryMoon 2018-02-08 05:04:55

试试能否将自己采纳为答案。。并不行

• liuyubobobo #1

  哈哈哈：）其实这种分享，如果愿意，也可以写在慕课网的手记中。写完以后，我去给你点赞：）

• 提问者 ShiveryMoon 回复 liuyubobobo #2

  哈哈，好，我也觉得写在这里怪怪的