LeetCode高频题73. 矩阵置零

编程入门行业动态更新时间:2024-10-23 19:20:03

LeetCode高频题73. <a href=https://www.elefans.com/category/jswz/34/1769510.html style= 矩阵置零"/>

LeetCode高频题73. 矩阵置零

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

文章目录

LeetCode高频题73. 矩阵置零
- @[TOC](文章目录)
题目
一、审题
最简单的就是外部辅助空间记录哪些行和列，需要变0
题目说了用：原地算法搞
总结

题目

给定一个 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]]

输入：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]]

提示：

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

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最简单的就是外部辅助空间记录哪些行和列，需要变0

当然，你遍历过程中，遇到0，不能立马改整行和整列，否则你待会不知道遇到的0是怎么来的

用一个行哈希表，列哈希表，记录哪些行，哪些列应该直接变零
耗费额外空间的

代码也很简单

        //复习：public void setZeroesReview(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;int N = matrix.length;int M = matrix[0].length;//辅助HashSet<Integer> rowSet = new HashSet<>();HashSet<Integer> columnSet = new HashSet<>();//遍历for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (matrix[i][j] == 0){rowSet.add(i);columnSet.add(j);}}}//再修改for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (rowSet.contains(i)) matrix[i][j] = 0;if (columnSet.contains(j)) matrix[i][j] = 0;}}}

测试；

    public static void test(){Solution solution = new Solution();int[][] arr = {{1,1,2,4},{3,1,5,2},{0,3,1,1},{1,3,1,0}};solution.setZeroes(arr);for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[0].length; j++) {System.out.print(arr[i][j] +" ");}System.out.println();}System.out.println();int[][] arr2 = {{1,1,2,4},{3,1,5,2},{0,3,1,1},{1,3,1,0}};solution.setZeroesReview(arr2);for (int i = 0; i < arr2.length; i++) {for (int j = 0; j < arr2[0].length; j++) {System.out.print(arr2[i][j] +" ");}System.out.println();}}public static void main(String[] args) {test();}

结果：

0 1 2 0 
0 1 5 0 
0 0 0 0 
0 0 0 0 0 1 2 0 
0 1 5 0 
0 0 0 0 
0 0 0 0

LeetCode测试:

外部辅助首先耗费空间
其次时间也挺慢

题目说了用：原地算法搞

咱们来一波节约空间和时间的做法

我们想干啥呢？？
用第0行来记录，这一行，是否要整体变0？？？
用第0列来记录，这一列，是否要整体变0？？？

如果遍历过程中，发现某一行i需要变0，那i行0列这个格子就要记录
如果遍历过程中，发现某一列j需要变0，那0行j列这个格子就要记录

那注意了
你万一第0行，需要整体变0，怎么记录，单独拿一个变量row0来记录，
你万一第0列，需要整体变0，怎么记录，单独拿一个变量column0来记录，

咱们一开始就先遍历0行，如果遇到0，row0=true
咱们一开始就先遍历0列，如果遇到0，column0=true

然后遍历i=1–N-1行，遍历j=1–M-1列，用第0行和0列记录
用0记录，回头你检查，不是0的都不要动，是0的整行，或者整列都得变0

然后变的时候，当然是根据0行和0列先搞0–N-1行和0–M-1列【注意这可是整个矩阵的行列都变哦】
然后检查row0和column0，决定整个0行和0列要不要变

这就是原地算法的意思
手撕代码：

        //如果遍历过程中，发现某一行i需要变0，那i行0列这个格子就要记录//如果遍历过程中，发现某一列j需要变0，那0行j列这个格子就要记录public void setZeroesSource(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;int N = matrix.length;int M = matrix[0].length;//俩变量记录//咱们一开始就先遍历0行，如果遇到0，row0=true//咱们一开始就先遍历0列，如果遇到0，column0=trueboolean row0 = false;boolean column0 = false;for (int i = 0; i < N; i++) {if (matrix[i][0] == 0) column0 = true;}for (int j = 0; j < M; j++) {if (matrix[0][j] == 0) row0 = true;}//然后遍历i=1--N-1行，遍历j=1--M-1列，用第0行和0列记录//用2记录，回头你检查，不是2的都不要动，是2的整行，或者整列都得变0for (int i = 1; i < N; i++) {for (int j = 1; j < M; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0;matrix[0][j] = 0;//对应俩格子记录0，代表这一行，这一列都得是0}}}//然后变的时候，当然是根据0行和0列先搞1--N-1行和1--M-1列//然后检查row0和column0，决定整个0行和0列要不要变for (int i = 1; i < N; i++) {for (int j = 1; j < M; j++) {if (matrix[i][0] == 0) matrix[i][j] = 0;//这一行都得是0if (matrix[0][j] == 0) matrix[i][j] = 0;//这一列都得是0}}if (row0)for (int j = 0; j < M; j++) {matrix[0][j] = 0;}if (column0)for (int i = 0; i < N; i++) {matrix[i][0] = 0;}}

测试

        System.out.println();int[][] arr3 = {{1,1,2,4},{3,1,5,2},{0,3,1,1},{1,3,1,0}};solution.setZeroesSource(arr3);for (int i = 0; i < arr3.length; i++) {for (int j = 0; j < arr3[0].length; j++) {System.out.print(arr3[i][j] +" ");}System.out.println();}

很OK