好的,我在这里是凌晨3点,所以很累,但是我第一次尝试对矩阵中的每个数字进行精确2次遍历,所以在O(NxN)中,矩阵的大小是线性的。
我使用第一列和第一行作为标记来知道哪里只有1的行/列。然后,有2个变量l和c可以记住第一个行/列是否也都是1。因此,第一遍设置标记并将其余的重置为0。
第二遍在行和列标记为1的位置设置1,并根据l和c重置第一行/列。
我强烈怀疑我能否一口气完成,因为一开始的方块取决于最后的方块。也许我的第二次通过可以变得更有效率…
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)