LeetCode之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.

Follow up:

Did you use extra space?
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?

【题意】

给定一个mxn的矩阵,如果一个元素是0,则它的整个行和列都设置为0。在原矩阵上进行操作。

你有没有使用额外的空间? 

直接使用为O(MN)的空间的方案可能并不是一个好的主意。 

一个简单的改进方案需要O(M + N)的空间,但仍然不是最好的解决方案。 

你可以制定一个连续的空间解决方案?

【分析】

  • 思路1:

O(m + n) 空间的方法很简单,设置两个数组,记录每行和每列是否存在 0。

  • 思路2:

想要常数空间,可以复用第一行和第一列作为辅助空间使用。不用开辟新的存储空间。其实第一行和第一列所在数组就是思路1中设置的数组,这样减少空间开销。

1.先确定第一行和第一列是否需要清零即,看看第一行中是否有0,记下来。也同时记下来第一列中有没有0。

2.扫描剩下的矩阵元素,如果遇到了0,就将该行第一个元素第一个元素赋值为0即赋值第一行数组和第一列数组。

这里不用担心会将本来第一行或第一列的1改成了0,因为这些值最后注定要成为0的。

3.根据第一行和第一列的信息,已经可以将剩下的矩阵元素赋值为结果所需的值了即,拿第一行为例,如果扫描到一个0,就将这一列都清0

4.根据1中确定的状态,处理第一行和第一列。如果最开始得到的第一行中有0的话,就整行清零。同理对列进行处理。

【代码1】

/*********************************
*   日期:2014-01-23
*   作者:SJF0115
*   题号: Set Matrix Zeroes
*   来源:http://oj.leetcode.com/problems/set-matrix-zeroes/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

class Solution {
public:
    //时间复杂度 O(m*n),空间复杂度 O(m+n)
    void setZeroes(vector<vector<int> > &matrix) {
        int i,j;
        int m = matrix.size();
        int n = matrix[0].size();
        //标记该行是否存在0
        vector<int> row(m,false);
        //标记该列是否存在0
        vector<int> col(n,false);
        //搜索0标记行列
        for(i = 0;i < m;i++){
            for(j = 0;j < n;j++){
                if(matrix[i][j] == 0){
                    col[j] = row[i] = true;
                }//if
            }//for
        }//for
        //如果某行存在0设置改行全为0
        for(i = 0;i < m;i++){
            if(row[i]){
                //设置为0
                for(j = 0;j < n;j++){
                    matrix[i][j] = 0;
                }//for
            }//if
        }//for
        //如果某列存在0设置改列全为0
        for(i = 0;i < n;i++){
            if(col[i]){
                //设置为0
                for(j = 0;j < m;j++){
                    matrix[j][i] = 0;
                }//for
            }//if
        }//for
    }
};
int main() {
    Solution solution;
    vector<int> row1 = {1,0,3,4};
    vector<int> row2 = {9,4,0,2};
    vector<int> row3 = {6,7,3,4};
    vector<vector<int>> matrix;
    matrix.push_back(row1);
    matrix.push_back(row2);
    matrix.push_back(row3);

    solution.setZeroes(matrix);
    int m = matrix.size();
    int n = matrix[0].size();
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            printf("%d ",matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}





【代码2】

/*********************************
*   日期:2014-01-23
*   作者:SJF0115
*   题号: Set Matrix Zeroes
*   来源:http://oj.leetcode.com/problems/set-matrix-zeroes/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

class Solution {
public:
    //时间复杂度 O(m*n),空间复杂度 O(1)
    void setZeroes(vector<vector<int> > &matrix) {
        //标记第一行是否有0
        bool rowZero = false;
        //标记第一列是否有0
        bool colZero = false;
        int i,j;
        int m = matrix.size();
        int n = matrix[0].size();
        //判断第一行是否有0
        for(i = 0;i < n;i++){
            if(matrix[0][i] == 0){
                rowZero = true;
            }//if
        }//for
        //判断第一列是否有0
        for(i = 0;i < m;i++){
            if(matrix[i][0] == 0){
                colZero = true;
            }//if
        }//for
        //搜索0进行标记
        for(i = 1;i < m;i++){
            for(j = 1;j < n;j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = matrix[0][j] = 0;
                }//if
            }//for
        }//for
        for(i = 1;i < m;i++){
            for(j = 1;j < n;j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }//if
            }//for
        }//for
        //第一行存有0则全设置为0
        if(rowZero){
            for(i = 0;i < n;i++){
                matrix[0][i] = 0;
            }
        }//if
        //第一列存有0则全设置为0
        if(colZero){
            for(i = 0;i < m;i++){
                matrix[i][0] = 0;
            }
        }//if
    }
};
int main() {
    Solution solution;
    vector<int> row1 = {1,2,3,4};
    vector<int> row2 = {9,4,0,2};
    vector<int> row3 = {6,7,3,4};
    vector<vector<int>> matrix;
    matrix.push_back(row1);
    matrix.push_back(row2);
    matrix.push_back(row3);

    solution.setZeroes(matrix);
    int m = matrix.size();
    int n = matrix[0].size();
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            printf("%d ",matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}







LeetCode之Set Matrix Zeroes

上一篇:UML概述


下一篇:NNIT第八届生命科学行业研讨会:医药信息化正在迎来数字化变革