73.矩阵置零
给定一个 *m* x *n*
的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1:
1 2
| 输入:matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[1,0,1],[0,0,0],[1,0,1]]
|
示例 2:
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]]
|
Solution
显然需要用到一种标记来表示这个零是后加的还是原生的,问题是,在要求原地算法的情况下,如何标记?题解给出了崭新的思路,利用数组本身的第1行和第1列作为标记,事先遍历记录第1行和第1列中零元素的位置,然后利用第1行和第1列作为数组置零的表示器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean flagCol0 = false, flagRow0 = false; for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { flagCol0 = true; break; } } for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { flagRow0 = true; break; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = matrix[0][j] = 0; } } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (flagCol0) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } if (flagRow0) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } } }
|