矩阵置零 - 中等

*************

c++

topic: 73. 矩阵置零 - 力扣（LeetCode）

*************

Look at the topic and I find a really new concept.

What is 原地算法, which is In-plcae Algorithm？

In-place Algorithm donot have to creat a new assistant space to store the data. Change the data exactly in the raw container.

Inspect a simple example. numbers = {1, 2, 3, 4, 5}, now how to change the numbers  from raw to numbers = {5, 4, 3, 2, 1}?

void reverseInPlace(std::vector<int> &nums)
{
    int start = 0;
    int end = nums.size() - 1;

    while (start < end)
    {
        // 交换首尾元素
        std::swap(nums[start], nums[end]);
        // 移动指针
        start++;
        end--;
    }
}

So the key point of the In-place algorithm is change thedata exactly in the raw data.

Inspect the topic and I find that I need some skills to change the elements in a matrix directly. I love basic soooooo much. I always addict in simlpe and useful things. When I in my own time, a question always comes to me, which is What kind of result is worthy of the upheaval of the journey? Is the result more important than the process? What is the result mean? But I think I can figure out the problems now. Life is full of pities. And the results are really matters? If get marriaged counts as a result, what about divorce? If dead counts as a result, what about half-dead? So I deceide to get involved in the process and experience all the things comes to me. It is myself who can deal with all the things. Like update the system, I update myself is really a proud thing. Results donot matter, accepting all the result matters.

Talking a little much today. And back.

The key point of the algorithm is iterating over all the  entire data. Visit all elements from left to right. And move to the next line and go on.

class Solution
{
public:
    void setZeroes(vector<vector<int>> &matrix)
    {
        int n = matrix.size(); // 行数
        int m = matrix[0].size(); // 列数

        for (int i = 0; i < n; i++)
        {
            // 遍历每一行
            for (int j = 0; j < m; j++)
            {
                // 遍历每一列
            }
        }
    }
};

if matrix[i][j] == 0

class Solution
{
public:
    void setZeroes(vector<vector<int>> &matrix)
    {
        int n = matrix.size(); // 行数
        int m = matrix[0].size(); // 列数

        for (int i = 0; i < n; i++)
        {
            // 遍历每一行
            for (int j = 0; j < m; j++)
            {
                // 遍历每一列
                if (matrix[i][j] == 0)
                {
                    // 如果元素为0，则将该行和该列的元素都置为0
                    for (int k = 0; k < n; k++)
                    {
                        matrix[k][j] = 0;
                    }
                    for (int k = 0; k < m; k++)
                    {
                        matrix[i][k] = 0;
                    }
                }
            }
        }
    }
};

I tend to define the code is right and the fact goes exactly the opposite way.

So the next step is that to find out where is wrong. Code never lies. Debug the code manually.

I find where is wrong.

   and step 14 matrix[1][1]=0 → 触发处理, then the matrix turn to ,

then skop to the step 25, matrix turn to . 

So if the program find matrix[i[[j[ == 0, remenber it and find next instead of changing the elements immediately. That is the way to make the errors happen. 

When find a 0 element in the matrix, flag it and move next. In the end, changes all the elements to 0. This concept sounds like a movie.

so In-place algorithm donot allow creating a assistant vector to store the data while the data has to be stored. Use the matrix it self. Use the first line and first column.

class Solution
{
public:
    void setZeroes(vector<vector<int>> &matrix)
    {
        int n = matrix.size(); // 行数
        int m = matrix[0].size(); // 列数

        for (int i = 0; i < n; i++)
        {
            // 遍历每一行
            for (int j = 0; j < m; j++)
            {
                // 遍历每一列
                if (matrix[i][j] == 0)
                {
                    // 如果元素为0，在第一行的第j列和第一列的第i行标记为0
                    matrix[0][j] = 0; // 第一行的第j列标记为0
                    matrix[i][0] = 0; // 第一列的第i行标记为0
                }
            }
        }

        // 遍历第一行，如果某个元素为0，则将该列的所有元素置为0
        for (int j = 1; j < m; j++)
        {
            if (matrix[0][j] == 0)
            {
                for (int i = 1; i < n; i++)
                {
                    matrix[i][j] = 0;
                }
            }
        }

        // 遍历第一列，如果某个元素为0，则将该行的所有元素置为0
        for (int i = 1; i < n; i++)
        {
            if (matrix[i][0] == 0)
            {
                for (int j = 1; j < m; j++)
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

And it almost right.

What if there is 0 element happens in the firstcolumn and row?

class Solution
{
public:
    void setZeroes(vector<vector<int>> &matrix)
    {
        int n = matrix.size(); // 行数
        int m = matrix[0].size(); // 列数

        bool firstRowZero = false; // 标记第一行是否有0
        bool firstColZero = false; // 标记第一列是否有0

        // 遍历第一行，检查是否有0
        for (int j = 0; j < m; j++)
        {
            if (matrix[0][j] == 0)
            {
                firstRowZero = true; // 第一行有0
                break;
            }
        }

        // 遍历第一列，检查是否有0
        for (int i = 0; i < n; i++)
        {
            if (matrix[i][0] == 0)
            {
                firstColZero = true; // 第一列有0
                break;
            }
        }

        // 遍历矩阵，标记第一行和第一列
        // 如果matrix[i][j]为0，则将第一行的第j列和第一列的第i行标记为0
        for (int i = 0; i < n; i++)
        {
            // 遍历每一行
            for (int j = 0; j < m; j++)
            {
                // 遍历每一列
                if (matrix[i][j] == 0)
                {
                    // 如果元素为0，在第一行的第j列和第一列的第i行标记为0
                    matrix[0][j] = 0; // 第一行的第j列标记为0
                    matrix[i][0] = 0; // 第一列的第i行标记为0
                }
            }
        }

        // 遍历第一行，如果某个元素为0，则将该列的所有元素置为0
        for (int j = 1; j < m; j++)
        {
            if (matrix[0][j] == 0)
            {
                for (int i = 1; i < n; i++)
                {
                    matrix[i][j] = 0;
                }
            }
        }

        // 遍历第一列，如果某个元素为0，则将该行的所有元素置为0
        for (int i = 1; i < n; i++)
        {
            if (matrix[i][0] == 0)
            {
                for (int j = 1; j < m; j++)
                {
                    matrix[i][j] = 0;
                }
            }
        }

        // 如果第一行有0，则将第一行的所有元素置为0
        if (firstRowZero)
        {
            for (int j = 0; j < m; j++)
            {
                matrix[0][j] = 0;
            }
        }

        // 如果第一列有0，则将第一列的所有元素置为0
        if (firstColZero)
        {
            for (int i = 0; i < n; i++)
            {
                matrix[i][0] = 0;
            }
        }
    }
};

and finally.

*************

Inspect the fastest program.

I think it is wrong because he creat a new space named record to store the data.

Then forget it.

Wish a magic vacation in the near future.