0 と 1 を含む NxN 行列が与えられます。a を含むすべての行をすべてs0に設定し0、a を含む0すべての列をすべて s に設定します0。
例えば
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
結果的に
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
Microsoft のエンジニアから、余分なメモリを必要とせず、2 つのブール変数と 1 つのパスだけを使用するソリューションがあると聞いたので、その答えを探しています。
ちなみに、これはビット マトリックスであると想像してください。したがって、マトリックスには 1 と 0 のみが許可されます。
ベストアンサー1
さて、ここは午前 3 時なので疲れていますが、行列内の各数値に対して正確に 2 回のパスを実行する最初の試行をすでに行っています。つまり、O(NxN) で、行列のサイズに比例します。
1 列目と 1 行目をマーカーとして使用して、1 のみの行/列がどこにあるかを確認します。次に、1 行目/列もすべて 1 であるかどうかを記憶するための 2 つの変数 l と c があります。したがって、最初のパスではマーカーを設定し、残りを 0 にリセットします。
2 番目のパスでは、行と列が 1 とマークされている場所に 1 を設定し、l と c に応じて 1 行目/列をリセットします。
最初の正方形は最後の正方形に依存するため、1 回のパスで完了できるかどうかは非常に疑問です。2 回目のパスはより効率的にできるかもしれません...
import pprint
m = [[1, 0, 1, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 1],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1]]
N = len(m)
### pass 1
# 1 rst line/column
c = 1
for i in range(N):
c &= m[i][0]
l = 1
for i in range(1,N):
l &= m[0][i]
# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
for j in range(1,N):
if m[i][j] == 0:
m[0][j] = 0
m[i][0] = 0
else:
m[i][j] = 0
### pass 2
# if line1 and col1 are ones: it is 1
for i in range(1,N):
for j in range(1,N):
if m[i][0] & m[0][j]:
m[i][j] = 1
# 1rst row and col: reset if 0
if l == 0:
for i in range(N):
m [i][0] = 0
if c == 0:
for j in range(1,N):
m [0][j] = 0
pprint.pprint(m)