Javascript每天一道算法题（十八）——矩阵置零-中等
文章目录
- 1、问题
- 2、示例
- 3、解决方法
- （1）方法1——标记数组
1、问题
给定一个 y x x 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
2、示例
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
111 101
101 => 000
111 101
示例 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]]
0120 0000
3452 => 0450
1215 0310
3、解决方法
（1）方法1——标记数组
思路：
1:用两个标记数组分别记录每一行和每一列是否有零出现。
2:遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true
3:最后我们再次遍历该数组，用标记数组更新原数组即可。
let matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
var setZeroes = function(matrix) {// 1:获取x，y轴的长度let y = matrix.length; // 1-1：二维数组的长度(矩阵y轴的长度)let x = matrix[0].length; // 1-2：一维数组的长度（矩阵x轴的长度）// 2：获取行和列的长度（注意：行的长度由列决定）let row = new Array(y).fill(false); // 2-1: 行(行的长度是列的多少决定的，如示例二有四列，行为4)let col = new Array(x).fill(false); // 2-2: 列(列的长度是行的多少决定的，如示例二有三行，列为3)// 3：双层遍历该数组，如果其中有一个元素为0，将当前的行和列改为truefor(let i =0;i<y;i++){for(let j =0;j<x;j++){if(matrix[i][j] == 0){row[i] = col[j] = true}}}// 4：再次双层循环该数组，将之前标记为true的数据设置为0for(let i =0;i<y;i++){for(let j =0;j<x;j++){if(row[i] || col[j]){matrix[i][j] = 0}}}// 5：输出结果console.log('zz', matrix);
};