LeetCode Technology

LeetCode 73. Set Matrix Zeroes(Medium)

查阅更多的题解,请点击

Problem

73. Set Matrix Zeroes(Medium)

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
    [1,1,1],
    [1,0,1],
    [1,1,1]
]
Output: 
[
    [1,0,1],
    [0,0,0],
    [1,0,1]
]

Example 2:

Input: 
[
    [0,1,2,0],
    [3,4,5,2],
    [1,3,1,5]
]
Output: 
[
    [0,0,0,0],
    [0,4,5,0],
    [0,3,1,0]
]

Follow up:

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

Solution

O(mn) time, O(1) space

这道题题意很清楚:矩阵中零元素所在的行和列全置为0,希望算法只用常数的额外存储空间。

对于该问题,首先要弄清楚为何需要额外的存储空间:用来存储遍历矩阵时零元素的行号和列号

比较常规的方法是用数组存储,在最坏情况下是O(n+m)space.有两种比较常规的优化思路:

  • 用一个变量尽可能多的表示所需表示的数据:比如可以用两个二进制数,第i位为0,表示第i行或者i列需置0
  • 用原来的空间存储需要记录的数据,这样方式需要覆盖原来的数据,则需该区域数据已经“无用”

第一种方法实现较为麻烦,因为m和n的长度可能过大,单个二进制无法表示。 第二种方法比较合适:

  • 对于查找到的第一个0元素,可以用该元素所在行(记为第i行)存储信息 若其后某行(记为k,k>i)存在0元素(列号为j),则设matrix[i-1][j-1]$,在该行结束后,将该行置为0 当遍历结束,第i行中所有0元素的列号标识了所有需要置0的列,将其全置为0后,将第i行也置为0,则结束

GitHub传送门

class Solution
{
  public:
    void setZeroes(vector<vector<int>> &matrix)
    {
        int m = matrix.size();
        int n = matrix[0].size();
        int posOfFirstZeroRow = -1;

        //find the row which can store 0-column
        for (int i = 0; i < m && posOfFirstZeroRow == -1; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == 0)
                {
                    posOfFirstZeroRow = i;
                    break;
                }
            }
        }
        if (posOfFirstZeroRow == -1)
            return;
        for (int i = posOfFirstZeroRow + 1; i < m; ++i)
        {
            bool flag = false;
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == 0)
                {
                    flag = true;
                    matrix[posOfFirstZeroRow][j] = 0;
                }
            }
            //set the row to 0
            if (flag)
            {
                for (int j = 0; j < n; ++j)
                    matrix[i][j] = 0;
            }
        }

        //set the value of 0-column
        for (int i = 0; i < n; ++i)
        {
            if (matrix[posOfFirstZeroRow][i] == 0)
            {
                for (int j = 0; j < m; ++j)
                    matrix[j][i] = 0;
            }
        }

        for (int i = 0; i < n; ++i)
            matrix[posOfFirstZeroRow][i] = 0;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注