桶排序以查找附近的几乎重复项

Question

我正在研究包含重复III的问题 -LeetCode

给定一个整数数组，找出是否有两个不同的索引我和Ĵ阵列中，使得绝对之间差NUMS [I]和NUMS [j]的**为至多吨和**绝对之间差我和j最多为k。

范例1：

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

范例2：

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

范例3：

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

阅读讨论区中的存储桶排序解决方案

class Solution2:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if t < 0: return False
        lookup = {}
        for i in range(len(nums)):
            b_idx = nums[i] // (t+1) 
            if b_idx in lookup:
                return True
            if b_idx - 1 in lookup and abs(nums[i] - lookup[b_idx - 1]) < t+1:
                return True
            if b_idx + 1 in lookup and abs(nums[i] - lookup[b_idx + 1]) < t+1:
                return True
            lookup[b_idx] = nums[i] 
            if i >= k: del lookup[nums[i-k] // (t+1)]
        return False    

解释

这个想法就像存储桶排序算法。假设我们有连续的存储桶，覆盖了num的范围，每个存储桶的宽度为（t + 1）。如果存在两个差值<= t的项目，则将发生以下两种情况之一：
（1）同一桶中
的两个桶（2）相邻桶中的两个桶

我知道存储桶排序的逻辑，但不知道此解决方案如何工作。

我认为，必须在宽度范围内的所有值之间进行比较，但解决方案仅比较同一存储桶和相邻存储桶，

del lookup[num[i-k]，我无法弄清楚此操作的目的。

Answer 1

第一个问题：为什么只比较同一个桶和相邻的桶？

(a, b)正如作者所说，if是有效对有两种情况：

(1) 两个在同一个桶中
(2) 两个在相邻桶中

如果b - a <= t只有上面说的两种情况，你可以通过这里的桶例子来理解：

<--a-- t+1 ---b-><----- t+1 -----> 在同一桶中
<----- t+1 --a--><- --b- t+1 -----> 在相邻桶中

Bucket这里使用 是因为我们想将范围划分为特定的宽度，并减少比较次数。这是一种用空间换时间的方法。

第二个问题：为什么del lookup[num[i-k]？

因为第二个限制是差值索引i，j所以最多应该是k。

因此，for i in range(len(nums)):如果 ，我们应该从存储桶中删除先前的索引 j i - j == k。并且包含了等于k的差值，因此我们应该在逻辑之后将其删除。

如果你不这样做，你会找到以下对abs(nums[i]-nums[j])<=t，但是abs(i-j)>t

我希望我说清楚了，如果您还有其他问题，请发表评论。:)

顺便说一句，一个建议：如果你感到困惑或卡住，你可以通过打印或调试来查看示例，你会更清楚，尤其是对于极端情况。