lc073

矩阵置零

1.问题描述

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

2.示例

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

示例 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]]

3.解题

为了不使用额外的空间，可以用矩阵的第一行和第一列作为两个标记数组。首先预处理出两个标记变量，记录第一行和第一列是否存在0元素。接着判断其他行与列：若行列中存在0元素，将对应的标记数组对应位置置为0。接着反过来使用第一行与第一列所标记的0去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。