题目链接:https://leetcode.com/problems/set-matrix-zeroes/
1. 题目介绍(Set Matrix Zeroes)Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.
【Translate】: 给定一个m × n的整数矩阵matrix,如果其中某一个元素是0,那么请将它的整行和整列都设置为0。
You must do it in place.
【Translate】: 在原矩阵上执行。
【测试用例】:
【条件约束】:
【跟踪】:
【Translate】:
- 使用O(mn)空间的直接解决方案可能不是一个好主意。
- 一个简单的改进使用O(m + n)空间,但仍然不是最好的解决方案。
- 你能设计一个常数空间解吗?
感觉这个思路就是很常规的思路,没有优化,只为了解题。首先一开始简单粗暴,遍历二维数组matrix,通过Map
// O(m+n) space.? class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; Map2.2 行首标记> map = new HashMap<>(); // 遍历matrix,记录元素为0的位置 for(int i = 0; i < m; i++){ ArrayList list = new ArrayList<>(); for(int j = 0; j < n; j++){ if(matrix[i][j] == 0){ list.add(j); } } map.put(i,list); } for(Integer key:map.keySet()){ List value = map.get(key); if(value.size() > 0){ for(int i = 0; i < n; i++){ matrix[key][i] = 0; } for (int j = 0; j < value.size(); j++) { // System.out.println("map = " + value.get(1)); for(int x = 0; x < m; x++){ matrix[x][value.get(j)] = 0; } } } } } }
原题解来自于dietpepsi的Java/Python O(1) space 11 lines solution。该题解首先通过一个while循环检查了第一行是否存在0元素,然后从第2行开始遍历所有元素,检查是否存在0元素,如果存在就将该元素对应的行首和列首置为0;随后反向检查元素,如果该元素的行首或列首有一项为0,那么就将该元素置为0;最后根据一开始while循环结果判断第一行是否存在0元素,如果存在,则将第一行全部置为0.
// O(1) space.? public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length, k = 0; // First row has zero? while (k < n && matrix[0][k] != 0) ++k; // Use first row/column as marker, scan the matrix for (int i = 1; i < m; ++i) for (int j = 0; j < n; ++j) if (matrix[i][j] == 0) matrix[0][j] = matrix[i][0] = 0; // Set the zeros for (int i = 1; i < m; ++i) for (int j = n - 1; j >= 0; --j) if (matrix[0][j] == 0 || matrix[i][0] == 0) matrix[i][j] = 0; // Set the zeros for the first row if (k < n) Arrays.fill(matrix[0], 0); }2.3 辅助数组标记
原题解来自于KnightY的My JAVA solution, easy to understand。该题解的思想确实和标题一样,易于理解,KnightY使用了行列两个辅助数组,通过一次遍历,记录下行列位置,之后再遍历一遍,如果行或列数组中该位置有标记,那么就将该元素置为0.
// O(m+n) space. class Solution { public void setZeroes(int[][] matrix) { int m=matrix.length; int n=matrix[0].length; int[] row = new int[m]; int[] col = new int[n]; for(int i=0;i3. 参考资料for(int j=0;j if(matrix[i][j]==0){ row[i]=1; col[j]=1; } } } for(int i=0;i for(int j=0;j if(row[i]==1||col[j]==1){ matrix[i][j]=0; } } } } }
[1] Arrays.fill()的用法 | CSDN