题目描述（中等难度）

给定一个矩阵，然后找到所有含有 0 的地方，把该位置所在行所在列的元素全部变成 0。

解法一

暴力解法，用一个等大的空间把给定的矩阵存起来，然后遍历这个矩阵，遇到 0 就把原矩阵的当前行，当前列全部变作 0，然后继续遍历。 1. public void setZeroes(int[][] matrix) { 2. int row = matrix.length; 3. int col = matrix[0].length; 4. int[][] matrix_copy = new int[row][col]; 5. //复制矩阵 6. for (int i = 0; i < row; i++) { 7. for (int j = 0; j < col; j++) { 8. matrix_copy[i][j] = matrix[i][j]; 9. } 10. } 11. for (int i = 0; i < row; i++) { 12. for (int j = 0; j < col; j++) { 13. //找到 0 的位置 14. if (matrix_copy[i][j] == 0) { 15. //将当前行，当前列置为 0 16. setRowZeroes(matrix, i); 17. setColZeroes(matrix, j); 18. } 19. 20. } 21. } 22. } 23. //第 col 列全部置为 0 24. private void setColZeroes(int[][] matrix, int col) { 25. for (int i = 0; i < matrix.length; i++) { 26. matrix[i][col] = 0; 27. } 28. } 29. //第 rol 行全部置为 0 30. private void setRowZeroes(int[][] matrix, int row) { 31. for (int i = 0; i < matrix[row].length; i++) { 32. matrix[row][i] = 0; 33. } 34. }

时间复杂度：O ( mn )。 空间复杂度：O（mn）。m 和 n 分别是矩阵的行数和列数。

解法二

空间复杂度可以优化一下，我们可以把哪一行有 0 ，哪一列有 0 都记录下来，然后最后统一把这些行，这些列置为 0。 1. public void setZeroes(int[][] matrix) { 2. int row = matrix.length; 3. int col = matrix[0].length; 4. //用两个 bool 数组标记当前行和当前列是否需要置为 0 5. boolean[] row_zero = new boolean[row]; 6. boolean[] col_zero = new boolean[col]; 7. for (int i = 0; i < row; i++) { 8. for (int j = 0; j < col; j++) { 9. //找到 0 的位置 10. if (matrix[i][j] == 0) { 11. row_zero[i] = true; 12. col_zero[j] = true; 13. } 14. } 15. } 16. //将行标记为 true 的行全部置为 0 17. for (int i = 0; i < row; i++) { 18. if (row_zero[i]) { 19. setRowZeroes(matrix, i); 20. } 21. } 22. //将列标记为 false 的列全部置为 0 23. for (int i = 0; i < col; i++) { 24. if (col_zero[i]) { 25. setColZeroes(matrix, i); 26. } 27. } 28. } 29. //第 col 列全部置为 0 30. private void setColZeroes(int[][] matrix, int col) { 31. for (int i = 0; i < matrix.length; i++) { 32. matrix[i][col] = 0; 33. } 34. } 35. //第 rol 行全部置为 0 36. private void setRowZeroes(int[][] matrix, int row) { 37. for (int i = 0; i < matrix[row].length; i++) { 38. matrix[row][i] = 0; 39. } 40. }

时间复杂度：O ( mn )。 空间复杂度：O（m + n）。m 和 n 分别是矩阵的行数和列数。 顺便说一下 leetcode 解法一说的解法，思想是一样的，只不过它没有用 bool 数组去标记，而是用两个 set 去存行和列。 1. class Solution { 2. public void setZeroes(int[][] matrix) { 3. int R = matrix.length; 4. int C = matrix[0].length; 5. Set rows = new HashSet(); 6. Set cols = new HashSet(); 7. 8. // 将元素为 0 的地方的行和列存起来 9. for (int i = 0; i < R; i++) { 10. for (int j = 0; j < C; j++) { 11. if (matrix[i][j] == 0) { 12. rows.add(i); 13. cols.add(j); 14. } 15. } 16. } 17. 18. //将存储的 Set 拿出来，然后将当前行和列相应的元素置零 19. for (int i = 0; i < R; i++) { 20. for (int j = 0; j < C; j++) { 21. if (rows.contains(i) || cols.contains(j)) { 22. matrix[i][j] = 0; 23. } 24. } 25. } 26. } 27. }

这里，有一个比自己巧妙的地方时，自己比较直接的用两个函数去将行和列分别置零，但很明显自己的算法会使得一些元素重复置零。而上边提供的算法，每个元素只遍历一次就够了，很棒。

解法三

继续优化空间复杂度，接下来用的思想之前也用过，例如41题解法二和47题解法二，就是用给定的数组去存我们需要的数据，只要保证原来的数据不丢失就可以。 按 47题解法二 的思路，就是假设我们对问题足够的了解，假设存在一个数，矩阵中永远不会存在，然后我们就可以把需要变成 0 的位置先变成这个数，也就是先标记一下，最后再统一把这个数变成 0。直接贴下leetcode解法二的代码。 1. class Solution { 2. public void setZeroes(int[][] matrix) { 3. int MODIFIED = -1000000; //假设这个数字不存在于矩阵中 4. int R = matrix.length; 5. int C = matrix[0].length; 6. 7. for (int r = 0; r < R; r++) { 8. for (int c = 0; c < C; c++) { 9. //找到等于 0 的位置 10. if (matrix[r][c] == 0) { 11. // 将需要变成 0 的行和列改为之前定义的数字 12. // 如果是 0 不要管，因为我们要找 0 的位置 13. for (int k = 0; k < C; k++) { 14. if (matrix[r][k] != 0) { 15. matrix[r][k] = MODIFIED; 16. } 17. } 18. for (int k = 0; k < R; k++) { 19. if (matrix[k][c] != 0) { 20. matrix[k][c] = MODIFIED; 21. } 22. } 23. } 24. } 25. } 26. 27. for (int r = 0; r < R; r++) { 28. for (int c = 0; c < C; c++) { 29. // 将是定义的数字的位置变成 0 30. if (matrix[r][c] == MODIFIED) { 31. matrix[r][c] = 0; 32. } 33. } 34. } 35. } 36. }

时间复杂度：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。 看下代码吧。 1. public void setZeroes(int[][] matrix) { 2. int row = matrix.length; 3. int col = matrix[0].length; 4. int free_row = -1; //记录第一个 0 出现的行 5. int free_col = -1; //记录第一个 0 出现的列 6. for (int i = 0; i < row; i++) { 7. for (int j = 0; j < col; j++) { 8. //如果是当前作为标记的列，就跳过 9. if (j == free_col) { 10. continue; 11. } 12. if (matrix[i][j] == 0) { 13. //判断是否是第一个 0 14. if (free_row == -1) { 15. free_row = i; 16. free_col = j; 17. //初始化行标记位为 0，如果之前是 0 就置为 1 18. for (int k = 0; k < matrix.length; k++) { 19. if (matrix[k][free_col] == 0) { 20. matrix[k][free_col] = 1; 21. } else { 22. matrix[k][free_col] = 0; 23. } 24. 25. } 26. //初始化列标记位为 0，如果之前是 0 就置为 1 27. for (int k = 0; k < matrix[free_row].length; k++) { 28. if (matrix[free_row][k] == 0) { 29. matrix[free_row][k] = 1; 30. } else { 31. matrix[free_row][k] = 0; 32. } 33. } 34. break; 35. //找 0 的位置，将相应的标志置 1 36. } else { 37. matrix[i][free_col] = 1; 38. matrix[free_row][j] = 1; 39. } 40. } 41. 42. } 43. } 44. if (free_row != -1) { 45. //将标志位为 1 的所有列置为 0 46. for (int i = 0; i < col; i++) { 47. if (matrix[free_row][i] == 1) { 48. setColZeroes(matrix, i); 49. } 50. } 51. //将标志位为 1 的所有行置为 0 52. for (int i = 0; i < row; i++) { 53. if (matrix[i][free_col] == 1) { 54. setRowZeroes(matrix, i); 55. } 56. } 57. } 58. } 59. 60. private void setColZeroes(int[][] matrix, int col) { 61. for (int i = 0; i < matrix.length; i++) { 62. matrix[i][col] = 0; 63. } 64. } 65. 66. private void setRowZeroes(int[][] matrix, int row) { 67. for (int i = 0; i < matrix[row].length; i++) { 68. matrix[row][i] = 0; 69. } 70. }

时间复杂度：O ( mn )。 空间复杂度：O（1）。 leetcode解法三和我的思想是一样的，它标记位直接用第一行和第一列，由于第一行和第一列不一定会被置为 0，所以需要用 isCol 变量来标记第一列是否需要置为 0，用 matrix[0][0] 标记第一行是否需要置为 0。它是将用 0 表示当前行（列）需要置 0，这一点也很巧妙，相比我上边的算法就不需要初始化标记位了。 1. class Solution { 2. public void setZeroes(int[][] matrix) { 3. Boolean isCol = false; 4. int R = matrix.length; 5. int C = matrix[0].length; 6. for (int i = 0; i < R; i++) { 7. //判断第 1 列是否需要置为 0 8. if (matrix[i][0] == 0) { 9. isCol = true; 10. } 11. //找 0 的位置，将相应标记置 0 12. for (int j = 1; j < C; j++) { 13. if (matrix[i][j] == 0) { 14. matrix[0][j] = 0; 15. matrix[i][0] = 0; 16. } 17. } 18. } 19. //根据标志，将元素置 0 20. for (int i = 1; i < R; i++) { 21. for (int j = 1; j < C; j++) { 22. if (matrix[i][0] == 0 || matrix[0][j] == 0) { 23. matrix[i][j] = 0; 24. } 25. } 26. } 27. 28. //判断第一行是否需要置 0 29. if (matrix[0][0] == 0) { 30. for (int j = 0; j < C; j++) { 31. matrix[0][j] = 0; 32. } 33. } 34. 35. //判断第一列是否需要置 0 36. if (isCol) { 37. for (int i = 0; i < R; i++) { 38. matrix[i][0] = 0; 39. } 40. } 41. } 42. }

总

这道题如果对空间复杂度没有要求就很简单了，对于空间复杂度的优化，充分利用给定的空间的思想很经典了。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情