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

Question

我正在处理问题 Contains Duplicate III - LeetCode

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

Example 1:

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

Example 2:

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

Example 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    

解释

The idea is like the bucket sort algorithm. Suppose we have consecutive buckets covering the range of nums with each bucket a width of (t+1). If there are two item with difference <= t, one of the two will happen:
(1) the two in the same bucket
(2) the two in neighbor buckets

我知道桶排序的逻辑，但不知道这个解决方案是如何工作的。

我认为，有必要比较所有具有宽度范围的值，但解决方案只比较相同的桶和相邻的桶，

del lookup[num[i-k]，我不明白这个操作的目的是什么。

Answer 1

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

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

(1) the two in the same bucket
(2) the two in neighbor buckets

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

<--a-- t+1 ---b-><----- t+1 -----> in same bucket
<----- t+1 --a--><---b- t+1 -----> in neighbor buckets

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

---

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

---

顺便提一个建议:如果你感到困惑或卡住了，你可以通过打印或调试的方式看一个例子，你会更清楚，尤其是对于角落案例。