[LeetCode 73] Set Matrix Zeroes

作者 Shilei Tian 日期 2016-05-16
[LeetCode 73] Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

非常有意思的一个题,但稍有不慎就会把整个矩阵全变成 0。这个题其实没什么道理可以讲,就是一些小技巧,下面先看一下代码,结合代码看一下用到了什么小技巧。

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

整体的思路就是,既然一个元素就可以决定整列和整行,那么我们就用第 0 列第 0 行的元素来作为标记。设置一个 col0 是为了标记在第 0 列里面这个元素 0 到底是矩阵本身就是 0 还是标记成 0 了,如果本身就是 0,也就是 col0 = true,那么在接下来的赋值过程中要把第一列所有的元素都赋成 0,但是这里有一个至关重要的一点:一定要在这一行元素处理完成后再进行第 0 列元素的赋值,否则就无法区分 0 的来源了。但是可能大家很疑惑,为什么行是从第 0 行开始的,而列确是从第一列开始的。其实也是可以从第 0 列开始的,只不过我们在迭代行的时候,上去就判断第一个元素是否为 0,因此再进行一次判断就多余了,仅仅是为了节省时间。但是大家可能又会问,那我跳过第 0 行,直接从第一行开始不就完了。如果这个矩阵行数大于 1 的话,这样做是没问题的;但是这里的边界条件一定要考虑清楚,有可能只有一行,那就没有第一行了,这样矩阵就不会变了。在下面赋值的过程也是用到了这个过程。

注意,我们赋值的时候是从矩阵的右下角开始的,这一步主要就是为了在这两层循环就能将赋值完成。否则话,只能从第一列和第一行开始,然后再根据第 0 行第 0 列的真实元素来重新将他们赋值。

这个题的思路还是蛮重要的,没有涉及什么重要的数据结构,也不是非常复杂的算法,仅仅就是要想到这样一个思路。当然,还有一种 O(mn) 空间复杂度的算法,是标记数组。