leetcode面试经典150题——37矩阵置零

题目： 矩阵置零

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

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
leetcode链接

方法一：使用额外数组标记
题目说对于每一个元素我们需要把它所在的行和列元素全部置为0，而我们一个矩阵有m行n列，因此我们需要定义两个数组，行数组和列数组用来记录该行元素是否需要置0，我们遍历矩阵的每一个元素，如果该元素为0，那么在行数组和列数组记录该元素的行和列，遍历结束后，我们最后对行数组和列数组进行遍历，把需要置0的行和列置0.
时间复杂度：o（m*n）
空间复杂度：o（m+n）

void setZeroes(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<int> nums1(n,0);//记录为0的行
    vector<int> nums2(m,0);//记录为0的列
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(matrix[i][j]==0){//把需要置0的行和列标记为1
                nums1[i] = 1;
                nums2[j] = 1;
            }
        }
    }
    for(int i=0;i<n;i++){
        if(nums1[i]==1){
            for(int j=0;j<m;j++){
                matrix[i][j] = 0;
            }
        }
    }
    for(int i=0;i<m;i++){
        if(nums2[i]==1){
            for(int j=0;j<n;j++){
                matrix[j][i] = 0;
            }
        }
    }
}

方法二：使用矩阵本身存储需要置0的行和列
在方法一中算法的时间复杂度为o(m+n)，而题目说需要原地求解，因此方法一不可行，因此我们考虑不申请额外的数组来存储需要置0的行和列，我们可以考虑用矩阵的第一行和第一列来存储需要置0的行和列，但是这么做会导致矩阵第一行第一列的元素被覆盖掉，因此我们先定义两个bool变量来记录第一行和第一列是否有为0的元素，然后再对其它元素进行遍历，将为0元素的行和列在第一行和第一列中相应的位置标记，遍历结束后，最后对第一行和第一列进行处理。
时间复杂度：o(m*n)
空间复杂度：o(1)

void setZeroes(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    bool row0 = false, col0 = false;
    //判断第一行是否有为0的元素
    for(int i=0;i<m;i++){
        if(matrix[0][i]==0){
            row0 = true;
            break;
        }
    }
    //判断第一列是否有为0的元素
    for(int i=0;i<n;i++){
        if(matrix[i][0]==0){
            col0 = true;
            break;
        }
    }
    //判断其它元素是否为0，并且用第一行和第一列记录为0的元素的行列
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(matrix[i][j]==0){
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    //判断其它元素是否处于需要置0的行列中
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(matrix[i][0]==0||matrix[0][j]==0){
                matrix[i][j] = 0;
            }
        }
    }
    //最后对第一行第一列进行单独处理，如果有为0的元素那么全部置0
    if(row0){
        for(int i=0;i<m;i++){
            matrix[0][i] = 0;
        }
    }
    if(col0){
        for(int i=0;i<n;i++){
            matrix[i][0] = 0;
        }
    }
}

方法三：方法二优化
在方法二中我们使用到了2个变量来存储第一行和第一列中是否有0的元素，其实我们可以只用一个变量col0来标记第一列是否有为0的元素，然后其它的操作和方法二一模一样，我们同样用第一行第一列来存储要置0的行列，但不同的是我们需要对除了第一列以外所有的元素进行遍历，考虑我们如果对第一行进行遍历，我们可能把本身不为0的元素把它置为了0（）第一行元素所在的行和列有0元素存在时候的情况），而我们第一行又是存储需要置0的列，此时我们修该了第一行，而我们遍历后面的元素后，我们使用了修改后的第一行的数据，因此我们会得到错误的答案，那么我们正确的做法应该是把第一行放到最后处理，所以我们从后往前来遍历每一行的元素。
时间复杂度：o(m*n)
空间复杂度：o(1)

void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false;//记录第一列是否有为0的元素
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {//将为0元素的行和列用第一行和第一列来标记
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
            if (flag_col0) {//处理第一列的数据
                matrix[i][0] = 0;
            }
        }
    }