algorithm - 微软面试 : transforming a matrix

Question

Given a matrix of size n x m filled with 0's and 1's

e.g.:

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

if the matrix has 1 at (i,j), fill the column j and row i with 1's

i.e., we get:

1 1 1 1 1

1 1 1 1 0

1 1 1 1 1

1 1 1 1 1

Required complexity: O(n*m) time and O(1) space

NOTE: you are not allowed to store anything except '0' or '1' in the matrix entries

以上是微软面试题。

我现在想了两个小时。我有一些线索，但不能再继续了。

---

好的。这个问题的第一个重要部分是即使使用直接的蛮力方式，也无法轻易解决。

如果我只是使用两个循环遍历矩阵中的每个单元格，并更改相应的行和列，则无法完成，因为生成的矩阵应该基于原始矩阵。

例如，如果我看到 a[0][0] == 1，我无法更改 row 0 和 column 0 所有到 1，因为这将影响 row 1，因为 row 1 最初没有 0。

---

我注意到的第二件事是，如果 r 行仅包含 0 而 c 列仅包含 0，则a[r][c]必须为0；对于不在此模式中的任何其他位置，应为 1。

那么另一个问题来了，如果我找到这样的行和列，我如何将相应的单元格 a[r][c] 标记为 special 因为它已经为 0。

---

我的直觉是我应该对此使用某种位操作。或者为了满足所需的复杂性，我必须做类似的事情，在我处理完 a[i][j] 之后，我应该继续处理 a[i+1][j+1]，而不是逐行或逐列扫描。

即使是不考虑时间复杂度的暴力破解，我也无法用其他条件解决。

有人知道吗？

---

解决方案:Java版

@japreiss 已经回答了这个问题，他/她的回答很聪明而且正确。他的代码是Python的，现在我给的是Java版本。致谢全部归于@japreiss

public class MatrixTransformer {

    private int[][] a;
    private int m;
    private int n;
    
    public MatrixTransformer(int[][] _a, int _m, int _n) {
        a = _a;
        m = _m;
        n = _n;
    }
    
    private int scanRow(int i) {
        int allZero = 0;
        for(int k = 0;k < n;k++)
            if (a[i][k] == 1) {
                allZero = 1;
                break;
            }
        
        return allZero;
    }
    
    private int scanColumn(int j) {
        int allZero = 0;
        for(int k = 0;k < m;k++)
            if (a[k][j] == 1) {
                allZero = 1;
                break;
            }
        
        return allZero;
    }
    
    private void setRowToAllOnes(int i) {
        for(int k = 0; k < n;k++)
            a[i][k] = 1;
    }
    
    private void setColToAllOnes(int j) {
        for(int k = 0; k < m;k++)
            a[k][j] = 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 overlap
//  firstRow = scanRow(0)
//  firstCol = scanCol(0)
//
//  # scan each column and store result in 1st row - O(mn) work
    
        
        
    public void transform() {
        int firstRow = scanRow(0);
        int firstCol = scanColumn(0);
                
                
        for(int k = 0;k < n;k++) {
            a[0][k] = scanColumn(k);
        }

        // 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

        for(int k = 0;k < m;k++) {
            a[k][0] = scanRow(k);
        }
        
        a[0][0] = firstCol | firstRow;
        
        for (int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                a[i][j] = a[0][j] | a[i][0];


        
        if (firstRow == 1) {
            setRowToAllOnes(0);
        }
        
        if (firstCol == 1) 
            setColToAllOnes(0);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i< m;i++) {
            for(int j = 0;j < n;j++) {
                sb.append(a[i][j] + ", ");
            }
            sb.append("\n");
        }
        
        return sb.toString();
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] a = {{1, 1, 0, 1, 0}, {0, 0, 0, 0, 0},{0, 1, 0, 0, 0},{1, 0, 1, 1, 0}};
        MatrixTransformer mt = new MatrixTransformer(a, 4, 5);
        mt.transform();
        System.out.println(mt);
    }

}

Answer 1

这是一个使用 2 个额外的 bool 存储的 python 伪代码解决方案。我认为它比我用英语做的更清楚。

def scanRow(i):
    return 0 if row i is all zeroes, else 1

def 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 overlap
firstRow = scanRow(0)
firstCol = scanCol(0)

# scan each column and store result in 1st row - O(mn) work
for 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) work
for 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) work
for 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 0
if firstRow:
    # set row 0 to all ones

if firstCol:
    # set col 0 to all ones