这是python伪代码的解决方案，使用了额外
bool的2个存储空间。我认为这比我用英语说得更清楚。
def scanRow(i): return 0 if row i is all zeroes, else 1def scanColumn(j): return 0 if col j is all zeroes, else 1# we're going to use the first row and column# of the matrix to store row and column scan values,# but we need aux storage to deal with the overlapfirstRow = scanRow(0)firstCol = scanCol(0)# scan each column and store result in 1st row - O(mn) workfor col in range(1, n): matrix[0, col] = scanColumn(col)# now row 0 tells us whether each column is all zeroes or not# it's also the correct output unless row 0 contained a 1 originally# do the same for rows into column 0 - O(mn) workfor row in range(1, m): matrix[row, 0] = scanRow(row)matrix[0,0] = firstRow or firstCol# now deal with the rest of the values - O(mn) workfor row in range(1, m): for col in range(1, n): matrix[row, col] = matrix[0, col] or matrix[row, 0]# 3 O(mn) passes!# go back and fix row 0 and column 0if firstRow: # set row 0 to all onesif firstCol: # set col 0 to all ones
