3

1 と 0 のみの配列があります。ここで、少なくとも K 0 を含む最小の連続したサブセット/サブアレイを見つけたいと考えています。

例 配列は 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 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 で開始 = 差分を diff に保存します。

次の増加差 8-15(指数差) 8-14(比較指数差)

そのため、要素が最も少ない要素を見つけるために動き続けます...

このソリューションのより良いアルゴリズムを探しています。

4

4 に答える 4

5

次のようなローリングウィンドウでできると思います：

  1. 指定された配列で、最初に出現する 0 を見つけます ( indexiなど)。
  2. ウィンドウに 0 が含まれるまでスキャンを続けますk(たとえば、ウィンドウは index で終了します)。jウィンドウの長さ (たとえばj-i+1=L) を記録します。
  3. ここで、 index で最も左の 0 を破棄し、i次の 0 を取得するまでスキャンを続けます (たとえば、 index で)i'
  4. にあるウィンドウの右端を拡張してj、j'0 のカウントをk再度 = にします。
  5. 新しいウィンドウの長さL'=j'-i'+1が小さい場合は、更新します。

jが配列の最後に到達するまで、上記の手順を繰り返します。

要素が最大 2 回スキャンされるため、余分なスペースは必要ありません。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個のゼロが得られるまでインデックスを見つけます。

ポインタを 2 つ用意します。

現在、ptr1 は最初のゼロが見られるインデックスにあります。開始 = ptr1

ptr2 は、k 個の 0 が見つかったインデックスにあります。

終了 = ptr2; a) ptr1 をインクリメントします。

b ) k 0 が見つかるまで、ptr2+1 からインデックスを見つけます。

c) ptr3 で K 0 を見つけたとします。ptr3-ptr1 < (end-start) の場合、インデックスの開始と終了を更新します。

リストの最後まで手順 a ～ c​​ を繰り返します。

最後に、開始と終了には、k​​ 0 があるインデックスがあります。

于 2012-12-06T11:12:19.690 に答える