leetcode笔记：Set Matrix Zeroes

一.题目描述

Given a

m*n

matrix, if an element is

, set its entire row and column to

. 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?

二.题目分析

该题目最直观的解法就是开辟一个新的矩阵，当原矩阵存在零元素的时候，就将新矩阵的对应行和列置为零。这样空间复杂度较高，也是题目不允许的。

若要做到空间复杂度为常数，我的做法是就是利用矩阵的第一行和第一列来作为标记使用，这样便不用开辟新的存储空间。具体方法：

1. 先确定第一行和第一列是否需要清零，即：遍历第一行中是否有 ，也同时记下第一列中有没有 。在以下代码中，使用bool型变量

   x_key

   和

   y_key

   分别记录第一行和第一列的情况；
2. 扫描剩下的矩阵元素，如果遇到了 ，就将该元素所对应的第一行和第一列上的元素赋值为 ；
3. 在遍历完二维数组后，就可以根据第一行和第一列的信息，将剩下的矩阵元素进行赋值。拿第一行为例，如果扫描到第

   i

   个元素为 ，就将二维数组的第

   i

   列全部置 ；
4. 最后，根据1中bool型变量

   x_key

   和

   y_key

   的值，处理第一行和第一列。如果最开始得到的第一行中有 的话，就整行清零，对第一列也采取同样的处理。

三.示例代码

第一种方法如下：

#include <vector>
using namespace std;

class Solution
{
public:
    // 时间复杂度O(m * n)，空间复杂度O(m + n)
    void setZeros(vector<vector<int> >& matrix)
    {
        const size_t x = matrix.size();
        const size_t y = matrix[].size();
        if (x ==  || y == ) return;
        vector<bool> rowRes(x, false);
        vector<bool> colRes(y, false);

        for (size_t i = ; i < x; i++)
        {
            for (size_t j = ; j < y; j++)
            {
                if (matrix[i][j] == )
                    rowRes[i] = colRes[j] = true;
            }
        }

        // set zero
        for (size_t i = ; i < x; i++)
        {
            if (rowRes[i])
                for (size_t k = ; k < x; k++)
                    matrix[i][k] = ;
        }
        for (size_t j = ; j < y; j++)
        {
            if (colRes[j])
                for (size_t k = ; k < x; k++)
                    matrix[k][j] = ;
        }
    }
};
           

以上方法的空间复杂度为

O(m + n)

，并不能达到题目要求的最终要求。

第二种方法如下：

#include <vector>
using namespace std;

class Solution
{
public:
    void setZerosBetter(vector<vector<int> >& matrix)
    {
        const size_t x = matrix.size();
        const size_t y = matrix[].size();
        bool x_key = false, y_key = false;
        if (x ==  || y == ) return;

        for (size_t i = ; i < y; i++)
        {
            if (matrix[][i] == )
            {
                x_key = true;
                break;
            }
        }

        for (size_t i = ; i < x; i++)
        {
            if (matrix[i][] == )
            {
                y_key = true;
                break;
            }
        }

        for (size_t i = ; i < x; i++)
        {
            for (size_t j = ; j < y; j++)
            {
                if (matrix[i][j] ==  && i >  && j > )
                {
                    matrix[i][] = ;
                    matrix[][j] = ;
                }
            }
        }
        // 调整1~x行、1~y列的元素
        for (size_t i = ; i < x; i++)
            if (matrix[i][] == )
            {
                for (size_t k = ; k < y; k++)
                    matrix[i][k] = ;
            }
        for (size_t j = ; j < y; j++)
            if (matrix[][j] == )
            {
                for (size_t k = ; k < x; k++)
                    matrix[k][j] = ;
            }

        // 最后调整第一行第一列

        if (y_key)
            for (size_t k = ; k < x; k++)
                matrix[k][] = ;

        if (x_key)
            for (size_t k = ; k < y; k++)
                matrix[][k] = ;
    }
};
           

四.小结

这道题如果只是仅仅想实现功能的话，不需要什么技巧，只有提高对空间复杂度的要求才能体现出算法设计的思想。