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

来源：4-8 二分搜索树底层实现的顺序性 Contain Duplicate III

ShiveryMoon

2018-02-08

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。

写回答

2回答