重庆网站建设模板,网站过程中遇到问题,儿童编程培训机构,宣传片拍摄的意义文章目录 一、题目二、C# 题解 一、题目 编写一种算法#xff0c;若M N矩阵中某个元素为0#xff0c;则将其所在的行与列清零。 点击此处跳转题目。
示例 1#xff1a; 输入#xff1a; [ [1,1,1], [1,0,1], [1,1,1] ] 输出#xff1a; [ [1,0,1], [0,0,0], [1,0,1] ] 示… 文章目录 一、题目二、C# 题解 一、题目 编写一种算法若M × N矩阵中某个元素为0则将其所在的行与列清零。 点击此处跳转题目。
示例 1 输入 [ [1,1,1], [1,0,1], [1,1,1] ] 输出 [ [1,0,1], [0,0,0], [1,0,1] ] 示例 2 输入 [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出 [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ] 二、C# 题解 此题有很多方法解无外乎都是记录需要清零的行与列这种写法太无聊了。这里提出一种递归的方式只需要遍历矩阵一次即可。当遇到 0 时使用 set0 变量记录该位置遍历完成后重置所有 set0。
public class Solution {public void SetZeroes(int[][] matrix) {BFS(ref matrix, 0, 0); // 广度优先遍历}public void BFS(ref int[][] matrix, int i, int j) {int m matrix.Length, n matrix[0].Length;if (i m j 0) return; // 递归出口// 计算下一个位置int next_i i, next_j j 1;if (next_j n) {next_j 0;next_i;}bool set0 matrix[i][j] 0; // 记录当前状态是否需要清零BFS(ref matrix, next_i, next_j); // 继续遍历// 最后执行清零if (set0) {for (int p 0; p n; p) matrix[i][p] 0;for (int q 0; q m; q) matrix[q][j] 0;}}
}时间复杂度 O ( m × n ) O(m\times n) O(m×n)。空间复杂度由矩阵中 0 出现的次数决定。 该方法依据元素记录因此当矩阵中 0 出现次数过多时会有重复操作只适合处理稀疏 0 矩阵。 矩阵中 0 过于密集时使用记录行列的方式会更好些但可能需要更多的空间和遍历次数。
