HHot 100C++ 图解

73. 矩阵置零

一句话套路借第一行第一列当标记位,O(1) 空间

题目描述

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

 

示例 1:

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:

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

 

提示:

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

 

进阶:

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

思路

时间O(mn)
空间O(1)

思路

用第 0 行 / 第 0 列作为「这一行/列要不要清零」的标记数组。

先单独记录第 0 行、第 0 列本身是否含 0,最后再处理它们。

顺序不能反

标记位写在最后处理,否则会被自己新写的 0 污染。

图解

j0 j1 j2 j3 i0 0 1 2 0 i1 3 4 5 2 i2 1 3 1 5
矩阵(来自本仓库测试数据,红色格子 = 0)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/06_matrix.cpp24 行
namespace lc0073 {
class Solution {
 public:
  void setZeroes(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return;  // 题面保证 m,n ≥ 1,本地防越界
    const int R = (int)matrix.size(), C = (int)matrix[0].size();
    bool zeroRow = false, zeroCol = false;
    for (int j = 0; j < C; ++j)
      if (matrix[0][j] == 0) zeroRow = true;
    for (int i = 0; i < R; ++i)
      if (matrix[i][0] == 0) zeroCol = true;
    for (int i = 1; i < R; ++i)
      for (int j = 1; j < C; ++j)
        if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;  // 打标记
    for (int i = 1; i < R; ++i)
      for (int j = 1; j < C; ++j)
        if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
    if (zeroRow)
      for (int j = 0; j < C; ++j) matrix[0][j] = 0;
    if (zeroCol)
      for (int i = 0; i < R; ++i) matrix[i][0] = 0;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q73_set_matrix_zeroes10 行
lc0073::Solution s;
vector<vector<int>> a{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
s.setZeroes(a);
CHECK_EQ(a, vector<vector<int>>({{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}));
vector<vector<int>> b{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
s.setZeroes(b);
CHECK_EQ(b, vector<vector<int>>({{0, 0, 0, 0}, {0, 4, 5, 0}, {0, 3, 1, 0}}));
vector<vector<int>> c{{1}};
s.setZeroes(c);
CHECK_EQ(c, vector<vector<int>>({{1}}));

↑↓ 选择↵ 打开/ 随时唤起