leetcode-73-Set-Matrix-Zeroes
题目描述(中等难度)
给定一个矩阵,然后找到所有含有 0 的地方,把该位置所在行所在列的元素全部变成 0。
解法一
暴力解法,用一个等大的空间把给定的矩阵存起来,然后遍历这个矩阵,遇到 0 就把原矩阵的当前行,当前列全部变作 0,然后继续遍历。
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
int[][] matrix_copy = new int[row][col];
//复制矩阵
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
matrix_copy[i][j] = matrix[i][j];
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//找到 0 的位置
if (matrix_copy[i][j] == 0) {
//将当前行,当前列置为 0
setRowZeroes(matrix, i);
setColZeroes(matrix, j);
}
}
}
}
//第 col 列全部置为 0
private void setColZeroes(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
//第 rol 行全部置为 0
private void setRowZeroes(int[][] matrix, int row) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
时间复杂度:O ( mn )。
空间复杂度:O(mn)。m 和 n 分别是矩阵的行数和列数。
解法二
空间复杂度可以优化一下,我们可以把哪一行有 0 ,哪一列有 0 都记录下来,然后最后统一把这些行,这些列置为 0。
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
//用两个 bool 数组标记当前行和当前列是否需要置为 0
boolean[] row_zero = new boolean[row];
boolean[] col_zero = new boolean[col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//找到 0 的位置
if (matrix[i][j] == 0) {
row_zero[i] = true;
col_zero[j] = true;
}
}
}
//将行标记为 true 的行全部置为 0
for (int i = 0; i < row; i++) {
if (row_zero[i]) {
setRowZeroes(matrix, i);
}
}
//将列标记为 false 的列全部置为 0
for (int i = 0; i < col; i++) {
if (col_zero[i]) {
setColZeroes(matrix, i);
}
}
}
//第 col 列全部置为 0
private void setColZeroes(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
//第 rol 行全部置为 0
private void setRowZeroes(int[][] matrix, int row) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
时间复杂度:O ( mn )。
空间复杂度:O(m + n)。m 和 n 分别是矩阵的行数和列数。
顺便说一下 class Solution {
public void setZeroes(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
Set<Integer> rows = new HashSet<Integer>();
Set<Integer> cols = new HashSet<Integer>();
// 将元素为 0 的地方的行和列存起来
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (matrix[i][j] == 0) {
rows.add(i);
cols.add(j);
}
}
}
//将存储的 Set 拿出来,然后将当前行和列相应的元素置零
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (rows.contains(i) || cols.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
}
这里,有一个比自己巧妙的地方时,自己比较直接的用两个函数去将行和列分别置零,但很明显自己的算法会使得一些元素重复置零。而上边提供的算法,每个元素只遍历一次就够了,很棒。 继续优化空间复杂度,接下来用的思想之前也用过,例如“>47题解法二,就是用给定的数组去存我们需要的数据,只要保证原来的数据不丢失就可以。解法三
class Solution {
public void setZeroes(int[][] matrix) {
int MODIFIED = -1000000; //假设这个数字不存在于矩阵中
int R = matrix.length;
int C = matrix[0].length;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
//找到等于 0 的位置
if (matrix[r][c] == 0) {
// 将需要变成 0 的行和列改为之前定义的数字
// 如果是 0 不要管,因为我们要找 0 的位置
for (int k = 0; k < C; k++) {
if (matrix[r][k] != 0) {
matrix[r][k] = MODIFIED;
}
}
for (int k = 0; k < R; k++) {
if (matrix[k][c] != 0) {
matrix[k][c] = MODIFIED;
}
}
}
}
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
// 将是定义的数字的位置变成 0
if (matrix[r][c] == MODIFIED) {
matrix[r][c] = 0;
}
}
}
}
}
时间复杂度:O ( mn )。
空间复杂度:O(1)。m 和 n 分别是矩阵的行数和列数。
当然,这个解法局限性很强,很依赖于样例的取值,我们继续想其他的方法。
回想一下解法二,我们用了两个 bool 数组去标记当前哪些行和那些列需要置零,我们能不能在矩阵中找点儿空间去存我们的标记呢?
可以的!因为当我们找到第一个 0 的时候,这个 0 所在行和所在列就要全部更新成 0,所以它之前的数据是什么就不重要了,所以我们可以把这一行和这一列当做标记位,0 当做 false,1 当做 true,最后像解法二一样,统一更新就够了。
如上图,找到第一个 0 出现的位置,把橙色当做解法二的列标志位,黄色当做解法二的行标志位。
如上图,我们首先需要初始化为 0,并且遇到之前是 0 的位置我们需要把它置为 1,代表当前行(或者列)最终要值为 0。
如上图,继续遍历找 0 的位置,找到后将对应的位置置为 1 即可。橙色部分的数字为 1 代表当前列要置为 0,黄色部分的数字为 1 代表当前行要置为 0。
看下代码吧。
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
int free_row = -1; //记录第一个 0 出现的行
int free_col = -1; //记录第一个 0 出现的列
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//如果是当前作为标记的列,就跳过
if (j == free_col) {
continue;
}
if (matrix[i][j] == 0) {
//判断是否是第一个 0
if (free_row == -1) {
free_row = i;
free_col = j;
//初始化行标记位为 0,如果之前是 0 就置为 1
for (int k = 0; k < matrix.length; k++) {
if (matrix[k][free_col] == 0) {
matrix[k][free_col] = 1;
} else {
matrix[k][free_col] = 0;
}
}
//初始化列标记位为 0,如果之前是 0 就置为 1
for (int k = 0; k < matrix[free_row].length; k++) {
if (matrix[free_row][k] == 0) {
matrix[free_row][k] = 1;
} else {
matrix[free_row][k] = 0;
}
}
break;
//找 0 的位置,将相应的标志置 1
} else {
matrix[i][free_col] = 1;
matrix[free_row][j] = 1;
}
}
}
}
if (free_row != -1) {
//将标志位为 1 的所有列置为 0
for (int i = 0; i < col; i++) {
if (matrix[free_row][i] == 1) {
setColZeroes(matrix, i);
}
}
//将标志位为 1 的所有行置为 0
for (int i = 0; i < row; i++) {
if (matrix[i][free_col] == 1) {
setRowZeroes(matrix, i);
}
}
}
}
private void setColZeroes(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
private void setRowZeroes(int[][] matrix, int row) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
时间复杂度:O ( mn )。
空间复杂度:O(1)。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程

本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com