假设您有一组数字和另一组数字.您必须找到包含所有数字且具有最小复杂性的最短子阵列.
数组可以有重复,让我们假设数字集不重复.它没有被排序 - 子数组可以包含任何顺序的数字集.
例如:
Array: 1 2 5 8 7 6 2 6 5 3 8 5
Numbers: 5 7
那么最短的子阵列显然是Array[2:5](python表示法).
另外,如果你想避免出于某种原因排序数组(在线算法),你会怎么做？
j_r*_*ker 15
我将写右扩展意味着将范围的右端点增加1,而左收缩意味着将范围的左端点增加1.这个答案是Aasmund Eldhuset答案的轻微变化.这里的区别在于,一旦我们找到最小的j使得[0,j]包含所有有趣的数字,我们此后仅考虑包含所有有趣数字的范围.(以这种方式解释Aasmund的答案是可能的,但也有可能将其解释为允许由于左收缩而丢失一个有趣的数字 - 一种尚未建立正确性的算法.)
基本思想是,对于每个位置j,我们将找到在位置j处结束的最短满足范围,假设我们知道在位置j-1处结束的最短满足范围.
编辑:修复了基本案例中的故障.
基本情况:找到最小的j',使得[0,j']包含所有有趣的数字.通过构造,可以没有包含所有有趣数字的范围[0,k <j'],因此我们不需要进一步担心它们.现在找到最小的最大i,使得[i,j']包含所有有趣的数字(即保持j'固定).这是在位置j'结束的最小满意范围.
为了找到在任意位置j处结束的最小满足范围,我们可以将在位置j-1处结束的最小满足范围向右延伸1个位置.此范围必然也包含所有有趣的数字,但它可能不是最小长度. 事实上,我们已经知道这是一个令人满意的范围意味着我们不必担心向左"向后"扩展范围,因为这只能在其最小长度上增加范围(即使解决方案更糟). 我们需要考虑的唯一操作是左收缩,它们保留了包含所有有趣数字的属性.因此,当此属性成立时,范围的左端点应尽可能地前进.当不能再进行左侧收缩时,我们将最小长度满足范围结束于j(因为进一步的左侧收缩显然不能使范围再次满足)并且我们已经完成了.
由于我们对每个最右边的位置j执行此操作,我们可以在所有最右边的位置采用最小长度范围来找到总体最小值.这可以使用嵌套循环来完成,其中j在每个外循环周期中前进.显然j提前1 n次.因为在任何时间点我们只需要j的前一个值的最佳范围的最左边位置,我们可以将其存储在i中,并在我们去时更新它.我从0开始,始终<= j <= n,并且只向上前进1,这意味着它最多可以前进n次.i和j都最多前进n次,这意味着算法是线性时间.
在下面的伪代码中,我将两个阶段组合成一个循环.如果我们已达到拥有所有有趣数字的阶段,我们只会尝试收缩左侧:
# x[0..m-1] is the array of interesting numbers.
# Load them into a hash/dictionary:
For i from 0 to m-1:
isInteresting[x[i]] = 1
i = 0
nDistinctInteresting = 0
minRange = infinity
For j from 0 to n-1:
If count[a[j]] == 0 and isInteresting[a[j]]:
nDistinctInteresting++
count[a[j]]++
If nDistinctInteresting == m:
# We are in phase 2: contract the left side as far as possible
While count[a[i]] > 1 or not isInteresting[a[i]]:
count[a[i]]--
i++
If j - i < minRange:
(minI, minJ) = (i, j)
count[]并且isInteresting[]是哈希/词典(如果涉及的数字很小,则为普通数组).
这听起来像是一个非常适合滑动窗口方法的问题:维护一个逐渐扩展和收缩的窗口(子阵列),并使用哈希图来跟踪每个"有趣"数字出现的次数.窗口.例如,从一个空窗口开始,然后通过添加后续元素(并使用hashmap跟踪哪些数字)将其展开为仅包含元素0,然后是元素0-1,然后是0-2,0-3等等.存在于窗口中).当hashmap告诉你窗口中存在所有有趣的数字时,你可以开始收缩它:例如0-5,1-5,2-5等,直到你发现窗口不再包含所有有趣的数字.然后,您可以再次开始在右侧扩展它,依此类推.我完全(但不完全)确定这对您的问题有效,并且可以实现在线性时间运行.