微软访谈:转换矩阵

Question

给定nxm的矩阵填充0和1

例如:

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

如果矩阵在(i,j)处有1,则用1​​填充列j和行i

即,我们得到:

1 1 1 1 1

1 1 1 1 0

1 1 1 1 1

1 1 1 1 1

所需复杂度:O(n*m)时间和O(1)空间

注意:您不能在矩阵条目中存储除"0"或"1"之外的任何内容

以上是Microsoft面试问题.

我想了两个小时了.我有一些线索,但不能再继续了.

---

好.这个问题的第一个重要部分是Even using a straight forward brute-force way,它不容易解决.

如果我只使用两个循环迭代矩阵中的每个单元格,并更改相应的行和列,则无法完成,因为生成的矩阵应基于原点矩阵.

例如,如果我看到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.

---

我的直觉是我应该对此使用某种位操作.或者为了满足所需的复杂性,我必须做类似的事情After I take care of a[i][j], I should then proceed to deal with a[i+1][j+1], instead of scan row by row or column by column.

即使对于没有考虑时间复杂性的蛮力,我也无法用其他条件来解决它.

任何人都有线索？

---

解决方案: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

这是python伪代码中的一个解决方案,它使用了2个额外bool的存储空间.我认为这比我用英语更清楚.

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

Answer 2

这是另一种直觉,为解决问题提供了一种简洁的算法.

使用O(n)空间的初始算法.

现在,让我们忽略O(1)内存约束.假设你可以使用O(n)内存(如果矩阵是m×n).这将使这个问题变得更加容易,我们可以使用以下策略:

• 创建一个布尔数组,每列一个条目.
• 对于每列,确定列中是否有任何1,并将该信息存储在相应的数组条目中.
• 对于每一行,如果行中有任何1,则将该行设置为全1.
• 对于每一列,如果设置了相应的数组条目,则将该列设置为全1.

作为示例,请考虑以下数组:

1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

我们首先创建并填充辅助数组,这可以通过一次访问每一列来及时完成O(mn).这显示在这里:

1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

1 1 1 1 0  <--- aux array

接下来,我们遍历行并填充每个行,如果它包含任何1.这给出了这个结果:

1 1 1 1 1
0 0 0 0 0
1 1 1 1 1
1 1 1 1 1

1 1 1 1 0  <--- aux array

最后,如果辅助阵列在该位置具有1,则我们用1填充每列.这显示在这里:

1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1

1 1 1 1 0  <--- aux array

所以有一个问题:这使用O(n)空间,我们没有!那么为什么甚至走这条路呢？

使用O(1)空间的修正算法.

事实证明,我们可以使用一个非常可爱的技巧来使用O(1)空间运行此算法.我们需要一个关键观察:如果每行包含至少一个1,则整个矩阵变为1.因此,我们首先看看是否是这种情况.如果是的话,太好了!我们完成了.

否则,矩阵中必须有一些全0的行.由于这一行都是0,我们知道在"填充包含1和1的每一行"步骤中,该行将不会被填充.因此,我们可以将该行用作我们的辅助数组!

让我们看看这个在行动.从这开始:

1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

现在,我们可以找到一个包含全0的行并将其用作辅助数组:

1 1 0 1 0
0 0 0 0 0  <-- Aux array
0 1 0 0 0
1 0 1 1 0

我们现在通过查看每个列并标记哪些包含至少一个1来填充辅助数组:

1 1 0 1 0
1 1 1 1 0  <-- Aux array
0 1 0 0 0
1 0 1 1 0

在这里填写1是完全安全的,因为我们知道他们无论如何都会被填补.现在,对于包含1的每一行(辅助数组行除外),我们用1填充这些行:

1 1 1 1 1
1 1 1 1 0  <-- Aux array
1 1 1 1 1
1 1 1 1 1

我们跳过辅助数组,因为最初它都是0,所以它通常不会被填充.最后,我们用辅助数组中的1填充每列1,给出最终结果:

1 1 1 1 1
1 1 1 1 0  <-- Aux array
1 1 1 1 1 
1 1 1 1 1

让我们再做一个例子.考虑这个设置:

1 0 0 0
0 0 1 0
0 0 0 0
0 0 1 0

我们首先找到一个全零的行,如下所示:

1 0 0 0
0 0 1 0
0 0 0 0 <-- Aux array
0 0 1 0

接下来,让我们通过标记包含1的列来填充该行:

1 0 0 0
0 0 1 0
1 0 1 0 <-- Aux array
0 0 1 0

现在,填写包含1的所有行:

1 1 1 1
1 1 1 1
1 0 1 0 <-- Aux array
1 1 1 1

接下来,用1代填充aux数组中包含1的所有列.这已经在这里完成了,我们得到了结果!

另一个例子,考虑这个数组:

1 0 0
0 0 1
0 1 0

这里的每一行至少包含一个1,所以我们只用一个填充矩阵并完成.

最后,让我们试试这个例子:

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

我们有很多辅助数组的选择,所以让我们选择第一行:

0 0 0 0 0 <-- aux array
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

现在,我们填写aux数组:

0 1 0 1 0 <-- aux array
0 0 0 0 0 
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

现在,我们填写行:

0 1 0 1 0 <-- aux array
0 0 0 0 0 
1 1 1 1 1
0 0 0 0 0
1 1 1 1 1

现在,我们根据aux数组填写列:

0 1 0 1 0 <-- aux array
0 1 0 1 0 
1 1 1 1 1
0 1 0 1 0
1 1 1 1 1

我们完成了!整个事情都在O(mn)时间运行,因为我们

• O(mn)是否可以找到辅助数组,如果不存在,O(mn)可能会立即工作.
• O(mn)是否可以填充辅助阵列.
• O(mn)是否可以填充包含1的行.
• O(mn)是否可以填充包含1的列.

另外,它只使用O(1)空间,因为我们只需要存储aux数组的索引和足够的变量来在矩阵上进行循环.

编辑:我有这个算法的Java实现,并在我的个人网站上详细描述了它.请享用!

希望这可以帮助!