如果该行或列包含0，则将矩阵中的每个单元格设置为0

小编典典

如果该行或列包含0，则将矩阵中的每个单元格设置为0

algorithm

想要改善这篇文章吗？ 提供此问题的详细答案，包括引文和答案正确的解释。答案不够详细的答案可能会被编辑或删除。

给定一个0x和1s的NxN矩阵。将包含a的每一行设置0为all 0，并将包含a的每一列设置0为all 0。

例如

结果是

一位微软工程师告诉我，有一种解决方案不涉及额外的内存，仅涉及两个布尔变量和一次传递，因此我正在寻找该答案。

顺便说一句，假设它是一个位矩阵，因此矩阵中只能包含1和0。

阅读 391

2020-07-28

共1个答案

小编典典

好的，我在这里是凌晨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)

2020-07-28