《Cracking the Coding Interview》——第1章：数组和字符串—

《Cracking the Coding Interview》——第1章：数组和字符串——题目7

2014-03-18 01:55

题目：给定一个MxN矩阵，如果某个元素为0，则将对应的整行和整列置为0。

解法：单独挑出一行和一列作为标记数组。因为某元素为0就全部置为0，所以不论A[i][j]为0中的j是几，第i行总会被置为0的。再用O(1)的额外空间去标记单独挑出的那一行一列是否包含0即可。要注意最后清零的顺序和范围不要错了。

代码：

  1 // 1.7 Write an algorithm such that if an element in an MxN matrx is 0, its antire row and column are set to 0.
  2 #include <cstdio>
  3 #include <vector>
  4 using namespace std;
  5 
  6 class Solution {
  7 public:
  8     void setMatrixZero(vector<vector<int> > &board) {
  9         int m, n;
 10         
 11         m = (int)board.size();
 12         if (m == 0) {
 13             return;
 14         }
 15         n = (int)board[0].size();
 16         if (n == 0) {
 17             return;
 18         }
 19         
 20         int i, j;
 21         bool row0_has_zero = false;
 22         bool col0_has_zero = false;
 23         for (i = 0; i < m; ++i) {
 24             if (board[i][0] == 0) {
 25                 col0_has_zero = true;
 26                 break;
 27             }
 28         }
 29         for (j = 0; j < n; ++j) {
 30             if (board[0][j] == 0) {
 31                 row0_has_zero = true;
 32             }
 33         }
 34         for (i = 1; i < m; ++i) {
 35             for (j = 1; j < n; ++j) {
 36                 if (board[i][j] == 0) {
 37                     board[i][0] = 0;
 38                     board[0][j] = 0;
 39                 }
 40             }
 41         }
 42         for (i = 1; i < m; ++i) {
 43             if (board[i][0] == 0) {
 44                 for (j = 1; j < n; ++j) {
 45                     board[i][j] = 0;
 46                 }
 47             }
 48         }
 49         for (j = 1; j < n; ++j) {
 50             if (board[0][j] == 0) {
 51                 for (i = 1; i < m; ++i) {
 52                     board[i][j] = 0;
 53                 }
 54             }
 55         }
 56         if (row0_has_zero) {
 57             for (j = 0; j < n; ++j) {
 58                 board[0][j] = 0;
 59             }
 60         }
 61         if (col0_has_zero) {
 62             for (i = 0; i < m; ++i) {
 63                 board[i][0] = 0;
 64             }
 65         }
 66     }
 67 };
 68 
 69 int main()
 70 {
 71     vector<vector<int> > board;
 72     int i, j;
 73     int m, n;
 74     Solution sol;
 75     
 76     while (scanf("%d%d", &m, &n) == 2 && (m || n)) {
 77         board.resize(m);
 78         for (i = 0; i < m; ++i) {
 79             board[i].resize(n);
 80         }
 81         for (i = 0; i < m; ++i) {
 82             for (j = 0; j < n; ++j) {
 83                 scanf("%d", &board[i][j]);
 84             }
 85         }
 86         sol.setMatrixZero(board);
 87         for (i = 0; i < m; ++i) {
 88             for (j = 0; j < n; ++j) {
 89                 if (j > 0) {
 90                     printf(" %d", board[i][j]);
 91                 } else {
 92                     printf("%d", board[i][j]);
 93                 }
 94             }
 95             printf("
");
 96         }
 97         printf("
");
 98     }
 99     
100     return 0;
101 }