leetcode筆記：Set Matrix Zeroes

一.題目描述

Given a m*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?

二.題目分析

該題目最直觀的解法就是開辟一個新的矩陣，當原矩陣存在零元素的時候，就將新矩陣的對應行和列置為零。這樣空間復雜度較高，也是題目不允許的。

若要做到空間復雜度為常數，我的做法是就是利用矩陣的第一行和第一列來作為標記使用，這樣便不用開辟新的存儲空間。具體方法：

先確定第一行和第一列是否需要清零，即：遍歷第一行中是否有0，也同時記下第一列中有沒有0。在以下代碼中，使用bool型變量x_key和y_key分別記錄第一行和第一列的情況；

掃描剩下的矩陣元素，如果遇到了0，就將該元素所對應的第一行和第一列上的元素賦值為0；

在遍歷完二維數組後，就可以根據第一行和第一列的信息，將剩下的矩陣元素進行賦值。拿第一行為例，如果掃描到第i個元素為0，就將二維數組的第i列全部置0；

最後，根據1中bool型變量x_key和y_key的值，處理第一行和第一列。如果最開始得到的第一行中有0的話，就整行清零，對第一列也采取同樣的處理。

三.示例代碼

第一種方法如下：

#include 
using namespace std;

class Solution
{
public:
    // 時間復雜度O(m * n)，空間復雜度O(m + n)
    void setZeros(vector >& matrix)
    {
        const size_t x = matrix.size();
        const size_t y = matrix[0].size();
        if (x == 0 || y == 0) return;
        vector rowRes(x, false);
        vector colRes(y, false);

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

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

以上方法的空間復雜度為O(m + n)，並不能達到題目要求的最終要求。

第二種方法如下：

#include 
using namespace std;

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

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

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

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

        // 最後調整第一行第一列

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

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

四.小結

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