博文中会简要介绍Leetcode P0073题目分析及解题思路。
“Set Matrix Zeroes”是一道比较简单的题目。
Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
Follow up:
- A straight forward 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?
根据题干中的问题，这道题的思路是递进式的。首先存储每个0的行列位置，然后再改变矩阵，这样的话需要的空间复杂度是O(mn)。
然后想到，相同行或者具有相同列的0元素其实无需重复记录，只要记录每个0元素的行或者列就行，无需记录每个0元素的坐标，这样一来只记录行或者列是否需要置为0，空间复杂度是O(m+n)。
最后既然整行和整列都需要变为0，那么在遇到0元素的时候可以直接将该元素所处的行的第一个元素和列的第一个元素置为0，当作一个标记，最后只需要扫一遍第一行和第一列即可以得到所有需要置为0的行列，则完成任务。这样一来空间复杂度是O(1)，因为没有额外使用空间记录，而是在矩阵第一行和第一列使用了标记。
以下是Java的题解代码实现。
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] zerosAtRow = new boolean[m];
boolean[] zerosAtCol = new boolean[n];
for (int r=0; r<m; ++r) {
for (int c=0; c<n; ++c) {
if (matrix[r][c] == 0) {
zerosAtRow[r] = true;
zerosAtCol[c] = true;
}
}
}
for (int r=0; r<m; ++r) {
if (zerosAtRow[r])
this.setZeroAtRow(r, m, n, matrix);
}
for (int c=0; c<n; ++c) {
if (zerosAtCol[c])
this.setZeroAtCol(c, m, n, matrix);
}
}
private void setZeroAtRow(int row, int m, int n, int[][] matrix) {
for (int c=0; c<n; ++c)
matrix[row][c] = 0;
}
private void setZeroAtCol(int col, int m, int n, int[][] matrix) {
for (int r=0; r<m; ++r)
matrix[r][col] = 0;
}
}
以下是C++的题解代码实现。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int height = matrix.size(), width = matrix[0].size();
vector<bool> row_check(height, false), col_check(width, false);
for (int row=0; row<height; ++row) {
for (int col=0; col<width; ++col) {
if (matrix[row][col] == 0) {
row_check[row] = true;
col_check[col] = true;
}
}
}
for (int row=0; row<height; ++row) {
if (row_check[row])
this->set_row_zero(matrix, row, width);
}
for (int col=0; col<width; ++col) {
if (col_check[col])
this->set_col_zero(matrix, col, height);
}
}
private:
void set_row_zero(vector<vector<int>> &matrix, int row, int width) {
for (int col=0; col<width; ++col)
matrix[row][col] = 0;
}
void set_col_zero(vector<vector<int>> &matrix, int col, int height) {
for (int row=0; row<height; ++row)
matrix[row][col] = 0;
}
};