首页 > 代码库 > leetcode第一刷_Set Matrix Zeroes

leetcode第一刷_Set Matrix Zeroes

这个题乍一看很简单,实际上还挺有技巧的。我最开始的想法是找一个特殊值标记,遇到一个0,把他所对应的行列中非零的元素标记成这个特殊值,0值保持不变,然后再从头遍历一次,碰到特殊值就转化成0。

问题是这个特殊值怎么确定,题目中没有把取值范围给出,我怀着侥幸的心理用了最大和最小的int,都被揪了出来。。如果找一个不存在于数组中的值,这个复杂度太高了。

有没有其他更好的方法呢?当然有。这个思想很巧妙,最后的结果是把所有0所在的行列都化成0,换句话说,化成0这个事情只要标记出是哪一行以及哪一列就可以了,能不能找到一种标记的方式来完成这个事情呢?做法是如果扫描到一个0,我们就把这个数的行列第一个数值置成0,用来做标记位,等全部扫描完毕后,针对为第一行和第一列为0的那些行列,置成0就可以了。

有一个细节,第一行和第一列该怎么办,他们可能一开始并没有0,因为标记的原因有0了,怎么区分呢?处理方式其实很简单,一开始先看一下它含不含0,然后在最后根据这个结果来决定要不要把他们变成0.

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