我在面试问题主题上遇到了这个问题.这是一个问题:
给定两个整数数组A [1..n]和B [1..m],找到A中包含B的所有元素的最小窗口.换句话说,找到一对<i,j>,使得A [i ..j]包含B [1..m].
如果A不包含B的所有元素,那么i,j可以返回-1.A中的整数不必与B中的整数相同.如果有多个最小窗口(不同,但具有相同的大小),那么它足以返回其中一个.
例如:A [1,2,5,11,2,6,8,24,101,17,8]和B [5,2,11,8,17].该算法应该返回i = 2(A中的索引为5)和j = 9(A中的索引为17).
现在我可以想到两种变化.
我们假设B有重复.
这种变化不考虑每个元素在B中出现的次数.它只检查B中出现的所有唯一元素,并找到满足上述问题的A中最小的对应窗口.例如,如果A [1,2,4,5,7]和B [2,2,5],这个变化并不打扰B中有两个2,只检查A中B的唯一整数即因此,返回i = 1,j = 3.
这种变化考虑了B中的重复.如果B中有两个2,那么它也希望在A中看到至少两个2.如果不是,则返回-1,-1.
当你回答时,请告诉我你要回答的变体.伪代码应该做.如果计算它很棘手,请提及空间和时间复杂度.提及您的解决方案是否假设数组索引也从1或0开始.
提前致谢.
以下在对数因子下可证明是最佳的.(我相信对数因子不能被消除,所以它是最优的.)
变量1只是变体2的一个特例,在从B中删除重复后,所有的多重性都是1.所以它足以处理后一种变体; 如果你想要变体1,只需及时删除重复项O(m log m).在下文中,让m我们假设B中不同元素的数量.我们假设m < n,因为否则我们可以-1在恒定时间内返回.
对于每个索引i中,我们会找到最小的指数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对于其c[k]=1在变体1,或c[k] = <the right number>在方案2).
因此,对于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.(这是摊销分析.)每次递增时j,您可能会执行需要O(log m)时间的设置操作,因此总时间为O(n log m).所需的空间用于保持计数的元组,B的元素集,集合S以及一些其他变量的常数,所以O(m)总的来说.
有一个明显的O(m+n) 下界,因为你需要检查所有元素.所以唯一的问题是我们能否证明这个log因素是必要的; 我相信它是.