修改矩阵并将列和行设置为零的算法

Question

这在技术上是一个代码挑战.有人问我一个有趣的问题,在接受记者采访时,我希望能为一些有识之士为最佳答案我可以想出是O(2N ^ 2) - N平方类别,但仍然非常强力.

假设你有一个M大小为N的矩阵(数组数组(int[][]))

1 2 4 3 1
0 5 3 7 7
5 8 9 2 8
6 7 0 8 9

如果单元格包含零,则将整个行和列设置为零.
结果如下:

0 2 0 3 1
0 0 0 0 0 
0 8 0 2 8
0 0 0 0 0 

最快和/或最好的方法是什么？

---

我自己的答案是迭代整个数组,跟踪行和列的归零,然后将它们归零.

public void zeroOut(int[][] myArray){
    ArrayList<Integer> rowsToZero = new....
    ArrayList<Integer> columnsToZero = new....

    for(int i=0; i<myArray.length; i++){ // record which rows and columns will be zeroed
        for(int j=0; j<myArray[i].length; i++){
            if(myArray[i][j] == 0){
                if(!rowsToZero.contains(i)) rowsToZero.add(i);
                if(!columnsToZero.contains(j)) columnsToZero.add(j);
            }
        }
    }
    for(int row : rows){ // now zero the rows
        myArray[row] = int[myArray.length];
    }

    for(int i=0; i<myArray.length; i++){
        for(int column: columns){ // now zero the columns
            myArray[i][column] = 0;
        }    
    }
}

有更好的算法吗？是否有更好的数据结构来表示这个矩阵？

Answer 1

到目前为止，似乎没有人真正想出一种明显更快/更好的算法，所以这个似乎就是这样。感谢大家的意见。

public void zeroOut(int[][] myArray){
    ArrayList<Integer> rowsToZero = new....
    ArrayList<Integer> columnsToZero = new....

    for(int i=0; i<myArray.length; i++){ // record which rows and columns will be zeroed
        for(int j=0; j<myArray[i].length; i++){
            if(myArray[i][j] == 0){
                if(!rowsToZero.contains(i)) rowsToZero.add(i);
                if(!columnsToZero.contains(j)) columnsToZero.add(j);
            }
        }
    }
    for(int row : rows){ // now zero the rows
        myArray[row] = int[myArray.length];
    }

    for(int i=0; i<myArray.length; i++){
        for(int column: columns){ // now zero the columns
            myArray[i][column] = 0;
        }    
    }
}