LeetCode 73. 矩阵置零

作者:Choi Yang

更新于:5 个月前

字数统计:899 字

阅读时长:4 分钟

阅读量:

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入: [
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1],
];
输出: [
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1],
];

示例 2:

输入: [
  [0, 1, 2, 0],
  [3, 4, 5, 2],
  [1, 3, 1, 5],
];
输出: [
  [0, 0, 0, 0],
  [0, 4, 5, 0],
  [0, 3, 1, 0],
];

进阶:

一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/set-matrix-zeroes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

用 O(n) 空间复杂度来做，先遍历矩阵，找到等于 0 的坐标，然后遍历坐标，将对应行和列置为 0 即可

时间复杂度 O(m * n)

javascript

var setZeroes = function (matrix) {
  let n = matrix.length;
  let m = matrix[0].length;
  let arr = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (matrix[i][j] == 0) {
        arr.push([i, j]);
      }
    }
  }
  while (arr.length) {
    let [x, y] = arr.pop();
    for (let i = 0; i < n; i++) matrix[i][y] = 0;
    for (let j = 0; j < m; j++) matrix[x][j] = 0;
  }
  return matrix;
};

另外一种，原地算法，空间复杂度 O(1)，我们无需借助外部空间。找到下标为 0 的坐标，然后直接对该行和该列不等于 0 的数字设置为 -0 即可。这里巧妙运用了 JS 中的 Object.is()方法，此时 0 和 -0 不相等，但是最终返回的矩阵还是为 0

javascript

var setZeroes = function (matrix) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[0].length; j++) {
      if (Object.is(matrix[i][j], 0)) {
        // 对行进行操作
        for (let k = 0; k < matrix.length; k++)
          if (!Object.is(matrix[k][j], 0) && k !== i) matrix[k][j] = -0;
        // 对列进行操作
        for (let k = 0; k < matrix[0].length; k++)
          if (!Object.is(matrix[i][k], 0) && k !== j) matrix[i][k] = -0;
      }
    }
  }
  return matrix;
};

cpp

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        bool row = false, col = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(matrix[i][j] == 0) {
                    if(i == 0) row = true;
                    if(j == 0) col = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if(row) {
            for(int i = 0; i < m; i++) {
                matrix[0][i] = 0;
            }
        }
        if(col) {
            for(int i = 0; i < n; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

java

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        boolean row = false, col = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(matrix[i][j] == 0) {
                    if(i == 0) row = true;
                    if(j == 0) col = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if(row) {
            for(int i = 0; i < m; i++) {
                matrix[0][i] = 0;
            }
        }
        if(col) {
            for(int i = 0; i < n; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        m = len(matrix[0])
        row = False
        col = False
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 0:
                    if i == 0:
                        row = True
                    if j == 0:
                        col = True
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        for i in range(1, n):
            for j in range(1, m):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        if row:
            for i in range(m):
                matrix[0][i] = 0
        if col:
            for i in range(n):
                matrix[i][0] = 0

学如逆水行舟，不进则退

Contributors

Choi Yang