73. Set Matrix Zeroes

🟠   🔖  数组 哈希表 矩阵  🔗 LeetCode

题目

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[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]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

Follow up:

• A straightforward 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?

题目大意

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

解题思路

• 此题考查对程序的控制能力，无算法思想；
• 题目要求采用原地的算法，所有修改即在原二维数组上进行；
• 在二维数组中有 2 个特殊位置，一个是第一行，一个是第一列，先用 2 个变量记录这一行和这一列中是否有 0，防止之后的修改覆盖了这 2 个地方；
• 然后除去这一行和这一列以外的部分判断是否有 0，如果有 0，将它们所在的行第一个元素和所在列的第一个元素标记为 0 ；
• 最后通过标记，将对应的行列置 0 即可。

代码

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  let first_row_has_zero = false;
  let first_line_has_zero = false;

  // 第一列是否有 0
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) {
      first_row_has_zero = true;
      break;
    }
  }
  // 第一行是否有 0
  for (let j = 0; j < n; j++) {
    if (matrix[0][j] === 0) {
      first_line_has_zero = true;
      break;
    }
  }
  // 除第一行、第一列外，其他地方有 0，则将列首和行首置为 0
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }
  // 遍历第一列，有 0 则将整行置为 0
  for (let i = 1; i < m; i++) {
    if (matrix[i][0] === 0) {
      for (let j = 1; j < n; j++) {
        matrix[i][j] = 0;
      }
    }
  }
  // 遍历第一行，有 0 则将整列置为 0
  for (let j = 1; j < n; j++) {
    if (matrix[0][j] === 0) {
      for (let i = 1; i < m; i++) {
        matrix[i][j] = 0;
      }
    }
  }
  // 若第一列原本有 0，则将第一列都置为 0
  if (first_row_has_zero) {
    for (let i = 0; i < m; i++) {
      matrix[i][0] = 0;
    }
  }
  // 若第一行原本有 0，则将第一行都置为 0
  if (first_line_has_zero) {
    for (let j = 0; j < n; j++) {
      matrix[0][j] = 0;
    }
  }
};

相关题目

相关题目

• 289. 生命游戏
• 2125. 银行中的激光束数量
• 🔒 Minimum Operations to Remove Adjacent Ones in Matrix
• 🔒 Remove All Ones With Row and Column Flips II

- [289. 生命游戏](https://leetcode.com/problems/game-of-life)
- [2125. 银行中的激光束数量](https://leetcode.com/problems/number-of-laser-beams-in-a-bank)
- [🔒 Minimum Operations to Remove Adjacent Ones in Matrix](https://leetcode.com/problems/minimum-operations-to-remove-adjacent-ones-in-matrix)
- [🔒 Remove All Ones With Row and Column Flips II](https://leetcode.com/problems/remove-all-ones-with-row-and-column-flips-ii)