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] = ;
    }
};
           

四.小結

這道題如果隻是僅僅想實作功能的話，不需要什麼技巧，隻有提高對空間複雜度的要求才能展現出算法設計的思想。