73. Set Matrix Zeroes
73.Set Matrix Zeroes
Given amxnmatrix, if an element is 0, set its entire row and column to 0. Do itin-place.
Example 1:
Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ]
Example 2:
Input: [ [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] ]
Follow up:
- A straight forward 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?
看到这个题目第一反应是,遍历一次矩阵,开辟两个数组,如果A[m][n] ==0,分别将行m,列n放到两个数组中,最后再遍历两个数组,将对应的行、列全部置为零。但是,这样在矩阵所有元素都为零的情况下,两个数组占用的空间就需要O(m+n),正好是题目Follow up中提到的,第二种不推荐的解法。尝试好久后,想到了最后AC的办法,主要思路是:
1、既然元素所在的行、列都要置零,这里借用数学中投影的概念,将需要置零的行、列记录在第一行和第一列。即如果A[m][n] == 0,那么 将A向左投影,令A[m][0]=0,向上投影,令A[0][n]=0;
2、分别循环第一列和第一行,将为0的元素,整行或整列置为0;
3、这里要注意第一行和第一列自己就包含0的情况,最好在纸上演示一遍。
具体代码如下:
public static void setZeroes(int[][] matrix) { if (matrix == null || 0 == matrix.length) { return; } int startCol = matrix[0][0]; int startRow = matrix[0][0]; int col = matrix[0].length; int row = matrix.length; for (int i = 0; i < col; i++) { if (0 == matrix[0][i]) { startRow = 0; } } for (int i = 0; i < matrix.length; i++) { if (0 == matrix[i][0]) { startCol = 0; } for (int j = 0; j < matrix[i].length; j++) { if (0 == matrix[i][j]) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < col; i++) { if (0 == matrix[0][i]) { for (int j = 0; j < row; j++) { matrix[j][i] = 0; } } } for (int i = 1; i < row; i++) { if (0 == matrix[i][0]) { for (int j = 0; j < col; j++) { matrix[i][j] = 0; } } } if (0 == startCol) { for (int i = 0; i < row; i++) { matrix[i][0] = 0; } } if (0 == startRow) { for (int i = 0; i < col; i++) { matrix[0][i] = 0; } } }
代码的后半部分:循环第一列和第一行,整行、整列置0,其实存在很多重复的置位操作(某些元素会被重复很多次置0),这里应该存在优化的可能。本人尝试多次后被leetcode的测试样例打败,暂时没想到理想的解法,后面可以做为改进点。
测试代码如下:
public static void main(String[] args) { int[][] martx = new int[][] { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } }; setZeroes(martx); for (int[] is : martx) { System.out.println(Arrays.toString(is)); } }
相关推荐
xceman 2020-09-22
bcbeer 2020-08-27
风萧萧梦潇 2020-08-17
夕加加 2020-07-20
LuckyDeng 2020-07-08
huangchunxia 2020-07-08
lbPro0 2020-07-05
葉無聞 2020-07-05
万里之书 2020-07-04
冰蝶 2020-07-04
yuzhongdelei0 2020-07-04
meiseeny 2020-06-28
RuoShangM 2020-06-28
bianxq 2020-06-28
80327065 2020-06-28
Codeeror 2020-06-28
somyjun 2020-06-25
xuanlvhaoshao 2020-06-16