leetcode 链接：零矩阵

题目

编写一种算法，若 M × N 矩阵中某个元素为 0，则将其所在的行与列清零。

示例：

  1. 输入：
  2. [
  3.   [1,1,1],
  4.   [1,0,1],
  5.   [1,1,1]
  6. ]
  7. 输出：
  8. [
  9.   [1,0,1],
  10.   [0,0,0],
  11.   [1,0,1]
  12. ]
  1. 输入：
  2. [
  3.   [0,1,2,0],
  4.   [3,4,5,2],
  5.   [1,3,1,5]
  6. ]
  7. 输出：
  8. [
  9.   [0,0,0,0],
  10.   [0,4,5,0],
  11.   [0,3,1,0]
  12. ]

解答 & 代码

这里给出一种原地算法，既不需要额外的空间：即使用第 0 行和第 0 列作标记数组，即让第 0 行、第 0 列的元素分别代表该列、该行是否包含 0。如果第 0 行的第 col 个元素为 0，则代表第 col 列含 0，要被全部置 0；如果第 row 行的第 0 个元素为 0，则代表第 row 行含 0，要被全部置 0

  • 首先分别遍历第 0 行、第 0 列的所有元素，确定第 0 行、第 0 列原本是否包含 0，分别用两个布尔变量 row0_cotain_0、col0_contain_0 表示
  • 修改标记数组：遍历除第 0 行、第 0 列外的所有元素，如果某个元素 matrix[row][col] 为 0，就将第 0 行、第 0 列对应元素即 matrix[0][col]、matrix[row][0] 置 0
  • 利用标记数组将需要置零的行、列（出去标记数组即第 0 行、第 0 列外）都置零

  • 根据两个布尔变量 row0_cotain_0、col0_contain_0 决定是否要将 第 0 行、第 0 列置 0

    1. class Solution {//原地算法，不需要额外空间
    2. public:
    3.   void setZeroes(vector<vector<int>>& matrix) {
    4.       int rows = matrix.size();
    5.       int cols = matrix[0].size();
    7.       int row0_cotain_0 = false;  //原本的第0行是否包含0
    8.       int col0_contain_0 = false; //原本的第0列是否包含0
    9.       //遍历第0行元素，如果包含0，则将row0_contain_0置为true
    10.       for(int col = 0; col < cols; ++col)
    11.       {
    12.           if(matrix[0][col] == 0)
    13.               row0_cotain_0 = true;
    14.       }
    15.       //遍历第0列元素，如果包含0，则将col0_contain_0置为true
    16.       for(int row = 0; row < rows; ++row)
    17.       {
    18.           if(matrix[row][0] == 0)
    19.               col0_contain_0 = true;
    20.       }
    22.       //用第0行和第0列作为两个标记数组，遍历其余行列元素，如果某个元素为0，则该列的第0个元素置0，该行的第0个元素置0，作为标记
    23.       //实际上，如果某个元素为0，则最终该行、该列的所有元素都要置0，因此这一步不用担心修改了第0行、第0列的元素
    24.       for(int row = 1; row < rows; ++row)
    25.       {
    26.           for(int col = 1; col < cols; ++col)
    27.           {
    28.               if(matrix[row][col] == 0)
    29.               {
    30.                   matrix[row][0] = 0;
    31.                   matrix[0][col] = 0;
    32.               }
    33.           }
    34.       }
    36.       //根据第0行、第0列这两个标记数组，将矩阵中（出去第0行、第0列）需要置零的行、列置零
    37.       for(int row = 1; row < rows; ++row)
    38.       {
    39.           for(int col = 1; col < cols; ++col)
    40.           {
    41.               if(matrix[row][0] == 0 || matrix[0][col] == 0)
    42.                   matrix[row][col] = 0;
    43.           }
    44.       }
    46.       //如果第0行原本就有0，则最后要将第0行元素全部置0
    47.       if(row0_cotain_0)
    48.       {
    49.           for(int col = 0; col < cols; ++col)
    50.               matrix[0][col] = 0;
    51.       }
    52.       //如果第0列原本就有0，则最后要将第0列元素全部置0
    53.       if(col0_contain_0)
    54.       {
    55.           for(int row = 0; row < rows; ++row)
    56.               matrix[row][0] = 0;
    57.       }
    58.   }
    59. };

    执行结果： ``` 执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 87.06% 的用户 内存消耗：11.8 MB, 在所有 C++ 提交中击败了 76.22% 的用户 ```