arrays - 囲まれた要素の効果的なピッキング

Question

1 0 0 0 1 0 1 0 1 1 1 両側1からゼロを効果的に見つける方法を順番に持っている場合.

このシーケンスでは、位置 6 と 8 のゼロを意味します。太字のもの。

1 0 0 0 1 0 1 0 1 1 1

配列をループして後ろと前を調べるアルゴリズムを想像できます。これは O(n) を意味するので、おそらくこれ以上滑らかなものはありません。

別の方法を見つけることができれば、私は興味があります。

Answer 1

使用strfind:

pos = strfind(X(:)', [1 0 1]) + 1

Xこれは がベクトルの場合にのみ機能することに注意してください。

例

X = [1 0 0 0 1 0 1 0 1 1 1 ];
pos = strfind(X(:)', [1 0 1]) + 1

結果：

pos =
     6     8

Answer 2

strfind@EitanT が提案した方法は非常に優れています。これを行う別の方法はfind、要素ごとのビット操作を使用することです。

% let A be a logical ROW array
B = ~A & [A(2:end),false] & [false,A(1:end-1)];
elements = find(B);

これは、例に基づいて、境界要素を除外することを前提としています。連結[A(2:end),false]と[false,A(1:end-1)]は、配列の長さを同じに保つために必要です。メモリが懸念される場合は、これらを排除できます。

% NB: this will work for both ROW and COLUMN vectors
B = ~A(2:end-1) & A(3:end) & A(1:end-2);
elements = 1 + find(B);  % need the 1+ because we cut off the first element above