算法:找到包含K 0的最小连续数组,其数组为1和0

Question

我只有1和0的数组.现在我想找到最小的连续子集/子阵列,其至少包含K 0.

示例数组是1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0和K(6)应该是0 0 1 0 1 1 0 0 0或0 0 0 0 1 0 1 1 0 ....

我的解决方案

     Array: 1 1 0 1 1 0 1 1 0  0  0  0  1  0  1  1  0  0  0   1  1  0  0
     Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  20 21 22 23
     Sum:   1 2 2 3 4 4 5 6 6  6  6  6  7  7  8  9  9  9  9  10 11 11 11
Diff(I-S):  0 0 1 1 1 2 2 2 3  4  5  6  6  7  7  7  8  9 10  10 10 11 12

对于K(6)

从9-15开始=在差异中存储差异.

下一个增加差异8-15(指数差异)8-14(比较指数差异)

所以继续前进,找到元素最少的元素......

我正在为这个解决方案寻找更好的算法.

Answer 1

我相信你可以用滚动的窗口做到:

1. 在给定的数组中,找到第一个出现的0(比如在索引处i).
2. 继续扫描,直到你k的窗口中包含0(例如,窗口以索引结束j)记录窗口长度(比如说j-i+1=L).
3. 现在,丢弃索引处最左边的0 i,并继续扫描直到你得到下一个0(比如索引i'
4. 扩展位于窗口的右端j,以j'使0的=计数k一次.
5. 如果新窗口长度L'=j'-i'+1较小,请更新它.
   
   

继续重复上述过程,直到j击中阵列结束.

不需要额外的空间和O(N)时间复杂度,因为元素最多扫描两次.