用Java替换矩阵中的零

我开始阅读著名的“破解编码面试”书，我想做以下练习。

编写算法，使得如果MxN矩阵中的元素为0，则其整个行和列均设置为0。

这是作者的解决方案：

public static void setZeros(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length;j++) {
        if (matrix[i][j] == 0) {
            row[i] = 1;
            column[j] = 1;
        }
    }
}

// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length; j++) {
        if ((row[i] == 1 || column[j] == 1)) {
             matrix[i][j] = 0;
        }
    }
 }
}

我同意作者的主要想法。我们不必在矩阵中存储“ 0”的位置，而只需存储相关行和列的位置。但是我在她的解决方案中发现了一个“奇怪”的地方，就是最后，她对矩阵的所有单元进行了循环，我认为这是不必要的。

这是我的解决方案：

static int[][] replaceMatrix(int[][] matrix){
  int M = matrix.length;
  int N = matrix[0].length;

  boolean[] row = new boolean[M] ;
  boolean[] column = new boolean[N];

  for (int i =0; i< M; i++) {
    for (int j = 0; j<N; j++ ){
         if (matrix[i][j] == 0) {
            row[i] = true;
            column[j] = true;
         }
    }
  }

  for (int i =0; i<M; i++){
    if (row[i]){
        for (int k =0; k<N; k++){
            matrix[i][k]=0;
        }
    }
  }

  for (int j =0; j<N; j++){
    if (column[j]){
        for (int k =0; k<M; k++){
            matrix[k][j]=0;
        }
    }
  }  

我是编程方面的新手，所以我对此不太确定。但是在我的解决方案中，如果除了第一步要存储0个位置，程序的第二部分的时间复杂度为O（M + N），而她的解决方案的复杂度为O（M * N）。

问题在于，一般复杂度将与具有复杂度O（2 * M * N）的O（M * N +（M + N））相同，不是吗？（我不确定）。例如，如果它是一个M = N的矩阵，那么两个程序的两个复杂度将为O（M ^ 2）。

我真的想知道在这种情况下复杂性是否有所不同？

ps：我读到可以使用位向量来改善空间复杂度。但是我真的不明白。您能给我一个大概的想法吗（用Java）？