python - 索引范围内的模糊重复项

Question

下面是一个 friend 被问到的面试题。我们都难住了。声明如下:

Consider an unsorted list of integers, A. Suppose A has size n. Suppose, further, that the element at index i has value x. We define two terms:

• A has "a duplicate in index range k" if the value x is at any of A[i-k], A[i-k+1],...,A[i-1],A[i+1],...,A[i+k] (i.e. k is the radius of the search across indicies)

• A has "a duplicate in value range d" if any element of A lies in the range x-d, x-d+1,...,x,x+1,...,x+d (i.e. d is the radius of the search across values)

In O(n) time and O(k) space, we want to know:

1. Does A have a duplicate in index range k?

2. Does A have a duplicate in index range k AND value range d?

第一个很简单:我们从索引 0 走到 n-1 并保留一组我们过去的 k 数字见过。如果我们当前的数字在我们添加之前已经在集合中，那么我们有一个副本。否则我们不这样做，我们会删除集合中最旧的元素以为新元素腾出空间。

第二个，我不知道。我可以想到 O(nd) 时间和 O(k) 空间的解决方案:保持与第一个问题相同的集合，但是，当我们点击 x 时，检查之间的每个数字x-d 和 x+d。但是我无法想象在空间或时间复杂度上都没有 d 的解决方案会是什么样子。我错过了什么？

Answer 1

您可以通过扩展第一种方法来完成第二部分。

不是将原始值存储在集合中，而是使用字典并存储除以 d+1 的值(映射到实际值)。

要点是我们可以确定没有 2 个值可以位于同一个 bin 中(或者它们相距比 d 更近)。

现在，当您扫描时，您需要检查垃圾箱以及两个相邻垃圾箱中可能发生的碰撞。

所以这是 O(3n) = O(n) 操作和 O(k) 空间。

示例 Python 代码

def check_for_duplicate(A,d,k):
    D = {} # Stores the previous 2k entries 
    for i,a in enumerate(A):
        b = a // (d+1)
        for delta in [-1,0,1]:
            if b+delta in D and abs(D[b+delta] - a) <= d:
                return True
        old = i - 2 * k
        if old >= 0:
            del D[ A[old] // (d+1) ]
        D[b] = a
    return False

print check_for_duplicate(A=[8,14],d=5,k=2)