算法：在1和0的數組中找到包含K 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）

開始與DIFF 9-15 =商店差。

下一頁增長差異 8-15（在折射率差） 8-14（比較折射率差）

於是就繼續前進，以找到至少元素元素...

我要找爲此解決方案提供更好的算法。

Answer 1

我相信你可以用滾動窗口做到這一點，如：

1. 在給定的陣列中，發現0第一次出現（在指數i說）。
2. 繼續掃描，直到你的窗口中包含0（包括0），記錄窗口長度（如j-i+1=L）。
3. 現在，丟棄最左邊的0索引i，並保持掃描，直到你得到下一個0（索引說i'
4. 擴展位於j到j'窗口的右端，使0的計= k一次。
5. 如果新的窗口長度L'=j'-i'+1較小更新它。
   
   

保持上重複上述過程，直到命中j數組的末尾。

不需要額外的空間，它的時間複雜度爲O(N)，因爲一個元素最多可以掃描兩次。

Answer 2

有了額外的O（k）內存，你可以在O（n）time.Here這是java代碼。你在做什麼，如果[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（））並找到最小值。同時我們移除第一個元素，並且再次添加最新索引維護隊列大小

Answer 3

1. 從開始掃描數組以找到索引，直到我們得到k個零。

有兩個指針。

現在ptr1位於可以看到第一個零的索引處。 start = ptr1

ptr2在我們找到k 0的索引處。

end = ptr2; a）增加ptr1。

b）從ptr2 + 1找到索引，直到找到k 0。

c）說在ptr3我們找到K 0的。如果ptr3-ptr1 <（結束開始）更新索引開始和結束。

重複步驟a -c直到列表結束。

最後，開始和結束的索引將有k個0。

Answer 4

完全正常的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