Set Matrix Zeroes

描述

Given a m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up: Did you use extra space?

A straight forward solution using O(mn) space is probably a bad idea.

A simple improvement uses O(m + n) space, but still not the best solution.

Could you devise a constant space solution?

分析

O(m+n)空间的方法很简单，设置两个bool数组，记录每行和每列是否存在0。

想要常数空间，可以复用第一行和第一列。

代码1

  1. // Set Matrix Zeroes
  2. // 时间复杂度O(m*n)，空间复杂度O(m+n)
  3. public class Solution {
  4.     public void setZeroes(int[][] matrix) {
  5.         final int m = matrix.length;
  6.         final int n = matrix[0].length;
  7.         boolean[] row = new boolean[m]; // 标记该行是否存在0
  8.         boolean[] col = new boolean[n]; // 标记该列是否存在0
  10.         for (int i = 0; i < m; ++i) {
  11.             for (int j = 0; j < n; ++j) {
  12.                 if (matrix[i][j] == 0) {
  13.                     row[i] = col[j] = true;
  14.                 }
  15.             }
  16.         }
  18.         for (int i = 0; i < m; ++i) {
  19.             if (row[i]) Arrays.fill(matrix[i], 0);
  20.         }
  21.         for (int j = 0; j < n; ++j) {
  22.             if (col[j]) {
  23.                 for (int i = 0; i < m; ++i) {
  24.                     matrix[i][j] = 0;
  25.                 }
  26.             }
  27.         }
  28.     }
  29. }

代码2

  1. // Set Matrix Zeroes
  2. // 时间复杂度O(m*n)，空间复杂度O(1)
  3. public class Solution {
  4.     public void setZeroes(int[][] matrix) {
  5.         final int m = matrix.length;
  6.         final int n = matrix[0].length;
  7.         boolean row_has_zero = false; // 第一行是否存在 0
  8.         boolean col_has_zero = false; // 第一列是否存在 0
  10.         for (int i = 0; i < n; i++)
  11.             if (matrix[0][i] == 0) {
  12.                 row_has_zero = true;
  13.                 break;
  14.             }
  16.         for (int i = 0; i < m; i++)
  17.             if (matrix[i][0] == 0) {
  18.                 col_has_zero = true;
  19.                 break;
  20.             }
  22.         for (int i = 1; i < m; i++)
  23.             for (int j = 1; j < n; j++)
  24.                 if (matrix[i][j] == 0) {
  25.                     matrix[0][j] = 0;
  26.                     matrix[i][0] = 0;
  27.                 }
  28.         for (int i = 1; i < m; i++)
  29.             for (int j = 1; j < n; j++)
  30.                 if (matrix[i][0] == 0 || matrix[0][j] == 0)
  31.                     matrix[i][j] = 0;
  32.         if (row_has_zero)
  33.             for (int i = 0; i < n; i++)
  34.                 matrix[0][i] = 0;
  35.         if (col_has_zero)
  36.             for (int i = 0; i < m; i++)
  37.                 matrix[i][0] = 0;
  38.     }
  39. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/set-matrix-zeroes.html