3

我只有 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(Difference in index) 8-14(Compare Difference in index)

所以继续寻找元素最少的元素......

我正在为此解决方案寻找更好的算法。

4

4 回答 4

5

我相信您可以使用滚动窗口来做到这一点，例如：

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

继续重复上述过程，直到j到达数组的末尾。

不需要额外的空间，而且O(N)时间复杂，因为一个元素最多会被扫描两次。

于 2012-12-06T11:12:36.777 回答
1

使用额外的 O(k) 内存，您可以在 O(n) 时间内完成。这是 java 代码。您正在做的是，如果 a[i]==0 则检查队列的第一个元素指向的位置。如果位置差异小于最小值，则更新答案。

Queue<Integer> queue =new LinkedList<Integer>();
int i=0;
while(queue.size()<k&&i<n)
{
if(a[i]==0)
{
queue.add(i);
}
i++;
}
if(i==n&&queue.size()<k)
System.out.println("Insufficient 0''s");
int ans=i-1-queue.peek();
for(int j=i;j<n;j++)
{
if(a[i]==0)
{
queue.poll();
queue.add(i);
ans=Math.min(ans,i-queue.peek());
}
}
System.out.println(ans);

编辑：解释

我们维护一个队列，该队列由所有位置为 0 的位置组成，并且我们将队列大小限制为 k。所以最初在 while 循环中，我们用前 k 个索引填充队列。如果看到所有元素后队列大小当然小于 k，那么这是不可能的。之后，我们继续遍历所有剩余的元素。每次看到 0 时，我们都会计算子序列的长度 (i-queue.peek()) 并找到最小值。此外，我们删除第一个元素，然后再次添加最新索引，保持队列大小

于 2012-12-06T11:02:25.677 回答
1

完全工作的python代码：

>>> A = "1 1 0 1 1 0 1 1 0  0  0  0  1  0  1  1  0  0  0   1  1  0  0".split()
>>> A = map(int, A)
>>> zero_positions = [i for i, x in enumerate(A) if x == 0]
>>> k = 3
>>> containing_k_zeros_intervals = zip(zero_positions, zero_positions[k:])
>>> min(b - a for a, b in containing_k_zeros_intervals)
3
于 2012-12-06T11:22:51.600 回答
0
  1. 从头开始扫描数组以找到索引，直到我们得到 k 个零。

有两个指针。

现在 ptr1 位于看到第一个零的索引处。开始 = ptr1

ptr2 位于我们找到 k 0 的索引处。

结束 = ptr2; a）增加ptr1。

b) 从 ptr2+1 中找到索引，直到我们找到 k 个 0。

c) 假设在 ptr3 我们找到 K 个 0。如果 ptr3-ptr1 < (end-start) 更新索引开始和结束。

重复步骤 a -c 直到列表结束。

最后， start 和 end 将有 k 个 0 的索引。

于 2012-12-06T11:12:19.690 回答