Google : 找最小窗口

Given array A and B, write a function to find the smallest window in A that covers all numbers in B

回复 1# wwwyhx
小声说一句，这题你前面发过了

这题应该能做到O(kn)。假设数组是a[1..n]和q[1..k]。
dp[n][k]: dp[ i][j]表示从a[ i]开始，包含q[j...k]的最小窗口的长度。初只全部设为INF。
for i = 1 to n
  if a[ i] == q[k]
    dp[ i][k] = 1;
for i = k-1 to 1
  p = -1;
  for j = n to 1
    if a[j] == q && p > 0
      dp[j][ i] = dp[p][i+1] + p - j;
    if a[j] == q[i+1]  p = j;
最后答案是dp[ i][1]之中最小的那个。
以上伪代码可能有漏洞，但大体思路是这样。假设某个位置a[ i]的值等于q[1]，要找严格从这个位置开始的最小窗口，我们总是可以用贪心的策略，找到第一个q[2]就继续找q3]，然后找到第一个q[3]就开始找 q[4]，跳过某个不会使解更优。所以每次内层循环我们只要维护一个离当前最近的q[i+1]的位置，直到找到一个q[ i]，然后可以直接通过dp[p][i+1]得出dp[j][ i]。细节还有可以简化的地方，空间好像也能优化到O(n)。欢迎指出漏洞。

回复  wwwyhx
小声说一句，这题你前面发过了

这题应该能做到O(kn)。假设数组是a[1..n]和q[1..k]。
dp[n][k]: dp[ i][j]表示从a[ i]开始，包含q[j...k]的最小窗口的长度。初只全部设为INF。
for i = 1 to n
  if a[ i] == q[k]
    dp[ i][k] = 1;
for i = k-1 to 1
  p = -1;
  for j = n to 1
    if a[j] == q && p > 0
      dp[j][ i] = dp + p - j;
    if a[j] == q  p = j;
最后答案是dp[ i][1]之中最小的那个。
以上伪代码可能有漏洞，但大体思路是这样。假设某个位置a[ i]的值等于q[1]，要找严格从这个 ...
darksteel 发表于 2011-5-23 03:37

不对吧，第一眼的感觉因该就是两个指针一个快一个慢，一开始都从起始点开始，不满足条件的话加快指针，满足条件后加慢指针缩小窗口，达到第一个最小窗口后移动一格慢指针使重新不满足条件，再次找第二个最小窗口，这样可以找出所有的最小窗口，记录最小的那个最小窗口。
要设计一个hash数据结构能方便的知道是否窗口能覆盖那个小数组

回复 3# wwwyhx
这个就是最朴素的办法吧，就是从每个位置都向后找一遍，这样最坏可能是n^2，虽然中间可以略过一些，但应该不会有本质的提高。我觉得是可以做到kn的

回复  wwwyhx
这个就是最朴素的办法吧，就是从每个位置都向后找一遍，这样最坏可能是n^2，虽然中间可以略过一些，但应该不会有本质的提高。我觉得是可以做到kn的
darksteel 发表于 2011-5-28 14:17

    不是O(n^2),是O(n)

编程很麻烦，道理就是这个，时间复杂度O(2n+m),空间复杂度O(m)，编程需要有些技巧来判断窗口的移动是否会让窗口从全部包含B到缺一个，或从不全包含到全包含，这两点做到O(1).

先用O(m)的时间复杂度建立O(m)的hashtable,  再用O(2n)的时间复杂度遍历A,遍历的过程不是O(n^2)的枚举。“两个指针一个快一个慢，一开始都从起始点开始，不满足条件的话加快指针，满足条件后加慢指针缩小窗口，达到第一个最小窗口后移动一格慢指针使重新不满足条件，再次找第二个最小窗口，这样可以找出所有的最小窗口，记录最小的那个最小窗口”， 就这个步骤的时间复杂度是O(2n)

hash node 的结构可以用
struct HASH_NODE
{
        int nVal; // 值
        int nFreqA; //当前在A窗口中出现的次数
        int nFreqB; //在B中出现的次数
        HASH_NODE* pNodeNxt;
}