73. 矩阵置零
73. 矩阵置零
题目
Given an m x n
integer matrix matrix
, if an element is 0
, set its entire row and column to 0
's.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1
Follow up:
- A straightforward 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?
题目大意
给定一个 m x n
的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
解题思路
- 此题考查对程序的控制能力,无算法思想;
- 题目要求采用原地的算法,所有修改即在原二维数组上进行;
- 在二维数组中有 2 个特殊位置,一个是第一行,一个是第一列,先用 2 个变量记录这一行和这一列中是否有 0,防止之后的修改覆盖了这 2 个地方;
- 然后除去这一行和这一列以外的部分判断是否有 0,如果有 0,将它们所在的行第一个元素和所在列的第一个元素标记为 0 ;
- 最后通过标记,将对应的行列置 0 即可。
代码
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
let first_row_has_zero = false;
let first_line_has_zero = false;
// 第一列是否有 0
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
first_row_has_zero = true;
break;
}
}
// 第一行是否有 0
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
first_line_has_zero = true;
break;
}
}
// 除第一行、第一列外,其他地方有 0,则将列首和行首置为 0
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 遍历第一列,有 0 则将整行置为 0
for (let i = 1; i < m; i++) {
if (matrix[i][0] === 0) {
for (let j = 1; j < n; j++) {
matrix[i][j] = 0;
}
}
}
// 遍历第一行,有 0 则将整列置为 0
for (let j = 1; j < n; j++) {
if (matrix[0][j] === 0) {
for (let i = 1; i < m; i++) {
matrix[i][j] = 0;
}
}
}
// 若第一列原本有 0,则将第一列都置为 0
if (first_row_has_zero) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
// 若第一行原本有 0,则将第一行都置为 0
if (first_line_has_zero) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
289 | 生命游戏 | [✓] | 数组 矩阵 模拟 | |
2123 | 使矩阵中的 1 互不相邻的最小操作数 🔒 | 图 数组 矩阵 | ||
2125 | 银行中的激光束数量 | 数组 数学 字符串 1+ | ||
2174 | 通过翻转行或列来去除所有的 1 II 🔒 | 位运算 广度优先搜索 数组 1+ |