leetcode：73. 矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

解答 & 代码

思想：用第 0 行的每一位 matrix[0][col] 代表对应的列 col 是否包含 0，用第 0 列的每一位 matrix[row][0] 代表对应的行 row 是否包含 0

• 另，需要预先使用额外的两个变量 row0Has0、col0Has0，分别记录第 0 行是否包含 0，第 0 列是否包含 0

  class Solution {
  public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        // 1. 用额外的两个变量分别记录第 0 行、第 0 列是否有 0，若有 0 则置为 true
        bool row0Has0 = false;        // 第 0 行是否包含 0
        bool col0Has0 = false;        // 第 0 列是否包含 0
        for(int col = 0; col < cols; ++col)
        {
            if(matrix[0][col] == 0)
            {
                row0Has0 = true;
                break;
            }
        }
        for(int row = 0; row < rows; ++row)
        {
            if(matrix[row][0] == 0)
            {
                col0Has0 = true;
                break;
            }
        }
  
        // 2. 遍历矩阵，如果某个元素 matrix[row][col] 为 0，标记该含有 0 即 matrix[row][0]，
        //       标记该列有 0 即 matrix[0][col] = 0
        for(int row = 1; row < rows; ++row)
        {
            for(int col = 1; col < cols; ++col)
            {
                if(matrix[row][col] == 0)
                {
                    matrix[0][col] = 0;
                    matrix[row][0] = 0;
                }
            }
        }
  
        // 3. 再次遍历矩阵，若元素所在行 or 列含 0，则将该元素置 0
        for(int row = 1; row < rows; ++ row)
        {
            for(int col = 1; col < cols; ++col)
            {
                if(matrix[0][col] == 0 || matrix[row][0] == 0)
                    matrix[row][col] = 0;
            }
        }
  
        // 4. 如果第 0 行含 0 ，则第 0 行置 0；如果第 0 列含 0，则第 0 列置 0
        if(row0Has0)
        {
            for(int col = 0; col < cols; ++col)
                matrix[0][col] = 0;
        }
        if(col0Has0)
        {
            for(int row = 0; row < rows; ++row)
                matrix[row][0] = 0;
        }
    }
  };
  

  复杂度分析：设矩阵 m 行 n 列

• 时间复杂度 O(mn)：

• 空间复杂度 O(1)：原地

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 76.20% 的用户
内存消耗：12.9 MB, 在所有 C++ 提交中击败了 37.66% 的用户