微软访谈：转换矩阵

微软访谈：转换矩阵

这是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