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. class Solution {
  4. public:
  5.     void setZeroes(vector<vector<int> > &matrix) {
  6.         const size_t m = matrix.size();
  7.         const size_t n = matrix[0].size();
  8.         vector<bool> row(m, false); // 标记该行是否存在0
  9.         vector<bool> col(n, false); // 标记该列是否存在0
  11.         for (size_t i = 0; i < m; ++i) {
  12.             for (size_t j = 0; j < n; ++j) {
  13.                 if (matrix[i][j] == 0) {
  14.                     row[i] = col[j] = true;
  15.                 }
  16.             }
  17.         }
  19.         for (size_t i = 0; i < m; ++i) {
  20.             if (row[i])
  21.                 fill(&matrix[i][0], &matrix[i][0] + n, 0);
  22.         }
  23.         for (size_t j = 0; j < n; ++j) {
  24.             if (col[j]) {
  25.                 for (size_t i = 0; i < m; ++i) {
  26.                     matrix[i][j] = 0;
  27.                 }
  28.             }
  29.         }
  30.     }
  31. };

代码2

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

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