确定包含另一个数组 B 的所有元素的数组 A 的索引 i..j 的算法

Question

我在一个面试问题线程中遇到了这个问题。这是问题:

Given two integer arrays A [1..n] andB[1..m], find the smallest windowin A that contains all elements ofB. In other words, find a pair < i , j >such that A[i..j] contains B[1..m].

If A doesn't contain all the elements ofB, then i,j can be returned as -1.The integers in A need not be in the same order as they are in B. If there are more than one smallest window (different, but have the same size), then its enough to return one of them.

Example: A[1,2,5,11,2,6,8,24,101,17,8] and B[5,2,11,8,17]. The algorithm should return i = 2 (index of 5 in A) and j = 9 (index of 17 in A).

现在我可以想到两种变体。

假设 B 有重复项。

1. 这个变体不考虑每个元素在B中出现的次数，它只是检查在B中出现的所有唯一元素，并在A中找到满足上述问题的最小对应窗口。例如，如果 A[1,2,4,5,7] 和 B[2,2,5]，这个变体不会在意 B 中有两个 2，而只是检查 A 中 B 中的唯一整数，即2 和 5，因此返回 i=1，j=3。

2. 此变体解释了 B 中的重复项。如果 B 中有两个 2，那么它预计在 A 中也至少会看到两个 2。如果不是，则返回 -1,-1。

当你回答时，请务必让我知道你在回答哪个变体。伪代码应该可以。如果计算起来很棘手，请提及空间和时间复杂度。提及您的解决方案是否也假定数组索引也从 1 或 0 开始。

提前致谢。

Answer 1

复杂性

时间:O((m+n)log m)

空间:O(m)

以下是可证明的最优对数因子。 (我相信对数因子不能去掉，所以它是最优的。)

变体 1 只是变体 2 的一个特例，在从 B 中删除重复项后，所有重数都为 1。因此足以处理后一个变体；如果您想要变体 1，只需删除 O(m log m) 中的重复项时间。在下面，让m表示 B 中不同元素的数量。我们假设 m < n , 因为否则我们只能返回 -1 , 在常数时间内。

对于每个索引 i在 A 中，我们会找到最小的索引 s[i]这样 A[i..s[i]]包含 B[1..m] , 具有正确的多重性。关键的观察结果是 s[i]是非递减的，这使我们能够在摊销的线性时间内做到这一点。

以 i=j=1 开头.我们将保留一个元组 (c[1], c[2], ... c[m]) B 每个元素在当前窗口中出现的次数 A[i..j] .我们还将保留一套 S计数“正确”的索引(1..m 的一个子集)(即 k，变体 1 中的 c[k]=1 或变体 2 中的 c[k] = <the right number>)。

因此，对于 i=1 , 从 j=1 开始, 增加每个 c[A[j]] (如果 A[j] 是 B 的一个元素)，检查 c[A[j]] 是否现在是“正确的”，并添加或删除 j来自 S因此。 S时停止尺寸 m .你现在找到了 s[1] , 至多 O(n log m)时间。 (有O(n) j 的，每组操作花费O(log m) 时间。)

现在计算连续的s[i] s，执行以下操作。增量i , 递减 c[A[i]] , 更新 S相应地，并在必要时增加 j直到 S尺寸 m再次。这给了你 s[i]对于每个 i .最后，报告(i,s[i])为此 s[i]-i是最小的。

请注意，尽管看起来您的表现可能高达 O(n)每个 j 的步骤(递增 i ) , 第二个指针 j只向右移动:所以你可以递增的总次数j最多是n . (这是 amortised analysis。)每次递增 j。 ，您可能会执行一个需要 O(log m) 的集合操作时间，所以总时间是O(n log m) .所需的空间用于保存计数元组、B 的元素集、集合 S 和一些常数的其他变量，所以 O(m)总之。

有一个明显的O(m+n) 下限，因为您需要检查所有元素。所以唯一的问题是我们是否可以证明 log因素是必要的；我相信是的。