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

我正在研究问题Contains Duplicate III - LeetCode



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

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

解释



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

我认为，有必要在宽度范围内的所有值之间进行比较，但是解决方案仅比较相同的存储桶和相邻的存储桶，
del lookup[num[i-k]，我无法弄清楚此操作的目的。

最佳答案

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

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



如果是b - a <= t，则只有上述两种情况，您可以在此处通过存储区示例了解它:



之所以使用Bucket是因为我们想将范围划分为偶数宽度，并减少比较时间。这是交换时间的一种方法。

第二个问题:为什么要使用del lookup[num[i-k]？

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

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

如果不这样做，您会发现一对abs(nums[i]-nums[j])<=t，但abs(i-j)>t的对

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

顺便提一句建议:如果您感到困惑或困惑，可以通过打印或调试来查看示例，您会更加清楚，尤其是在极端情况下。

关于python - 桶排序以查找附近的几乎重复项，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55565772/