daily leetcode - set-matrix-zeroes - !

题目地址

https://leetcode.com/problems/set-matrix-zeroes/

题目描述

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(m**n) 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?

思路

据说这题是CareerCup上的原题,我还没有刷CareerCup,所以不知道啦,不过这题也不算难,虽然我也是看了网上的解法照着写的,但是下次遇到绝对想的起来。这道题中说的空间复杂度为O(mn)的解法自不用多说,直接新建一个和matrix等大小的矩阵,然后一行一行的扫,只要有0,就将新建的矩阵的对应行全赋0,行扫完再扫列,然后把更新完的矩阵赋给matrix即可,这个算法的空间复杂度太高。将其优化到O(m+n)的方法是,用一个长度为m的一维数组记录各行中是否有0,用一个长度为n的一维数组记录各列中是否有0,最后直接更新matrix数组即可。这道题的要求是用O(1)的空间,那么我们就不能新建数组,我们考虑就用原数组的第一行第一列来记录各行各列是否有0.

  • 先扫描第一行第一列,如果有0,则将各自的flag设置为true
  • 然后扫描除去第一行第一列的整个数组,如果有0,则将对应的第一行和第一列的数字赋0
  • 再次遍历除去第一行第一列的整个数组,如果对应的第一行和第一列的数字有一个为0,则将当前值赋0
  • 最后根据第一行第一列的flag来更新第一行第一列

代码如下:

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();
        bool rowZero = false, colZero = false;
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) colZero = true;
        }
        for (int i = 0; i < n; ++i) {
            if (matrix[0][i] == 0) rowZero = true;
        } 
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowZero) {
            for (int i = 0; i < n; ++i) matrix[0][i] = 0;
        }
        if (colZero) {
            for (int i = 0; i < m; ++i) matrix[i][0] = 0;
        }
    }
};

思路2

符合直觉的想法是,使用一个 m + n 的数组来表示每一行每一列是否”全部是 0“,
先遍历一遍去构建这样的 m + n 数组,然后根据这个 m + n 数组去修改 matrix 即可。

mark

这样的时间复杂度 O(m * n), 空间复杂度 O(m + n).

代码如下:

var setZeroes = function(matrix) {
  if (matrix.length === 0) return matrix;
  const m = matrix.length;
  const n = matrix[0].length;
  const zeroes = Array(m + n).fill(false);

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const item = matrix[i][j];

      if (item === 0) {
        zeroes[i] = true;
        zeroes[m + j] = true;
      }
    }
  }

  for (let i = 0; i < m; i++) {
    if (zeroes[i]) {
      matrix[i] = Array(n).fill(0);
    }
  }

  for (let i = 0; i < n; i++) {
    if (zeroes[m + i]) {
      for (let j = 0; j < m; j++) {
        matrix[j][i] = 0;
      }
    }
  }

  return matrix;
};

但是这道题目还有一个follow up, 要求使用O(1)的时间复杂度。因此上述的方法就不行了。
但是我们要怎么去存取这些信息(哪一行哪一列应该全部为0)呢?

一种思路是使用第一行第一列的数据来代替上述的zeros数组。 这样我们就不必借助额外的存储空间,空间复杂度自然就是O(1)了。

由于我们不能先操作第一行和第一列, 因此我们需要记录下”第一行和第一列是否全是0“这样的一个数据,最后根据这个信息去
修改第一行和第一列。

具体步骤如下:

  • 记录下”第一行和第一列是否全是0“这样的一个数据
  • 遍历除了第一行和第一列之外的所有的数据,如果是0,那就更新第一行第一列中对应的元素为0

你可以把第一行第一列看成我们上面那种解法使用的m + n 数组。

  • 根据第一行第一列的数据,更新matrix
  • 最后根据我们最开始记录的”第一行和第一列是否全是0“去更新第一行和第一列即可

mark

关键点解析

  • 使用第一行和第一列来替代我们m + n 数组
  • 先记录下”第一行和第一列是否全是0“这样的一个数据,否则会因为后续对第一行第一列的更新造成数据丢失
  • 最后更新第一行第一列

代码

  • 语言支持:JS,Python3
/*
 * @lc app=leetcode id=73 lang=javascript
 *
 * [73] Set Matrix Zeroes
 */
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
  if (matrix.length === 0) return matrix;
  const m = matrix.length;
  const n = matrix[0].length;

  // 时间复杂度 O(m * n), 空间复杂度 O(1)
  let firstRow = false; // 第一行是否应该全部为0
  let firstCol = false; // 第一列是否应该全部为0

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const item = matrix[i][j];
      if (item === 0) {
        if (i === 0) {
          firstRow = true;
        }
        if (j === 0) {
          firstCol = true;
        }
        matrix[0][j] = 0;
        matrix[i][0] = 0;
      }
    }
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      const item = matrix[i][j];
      if (matrix[0][j] == 0 || matrix[i][0] == 0) {
        matrix[i][j] = 0;
      }
    }
  }

  // 最后处理第一行和第一列

  if (firstRow) {
    for (let i = 0; i < n; i++) {
      matrix[0][i] = 0;
    }
  }

  if (firstCol) {
    for (let i = 0; i < m; i++) {
      matrix[i][0] = 0;
    }
  }

  return matrix;
};

Python3 Code:

直接修改第一行和第一列为0的解法:

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        def setRowZeros(matrix: List[List[int]], i:int) -> None:
            C = len(matrix[0])
            matrix[i] = [0] * C
        
        def setColZeros(matrix: List[List[int]], j:int) -> None:
            R = len(matrix)
            for i in range(R):
                matrix[i][j] = 0
            
        isCol = False
        R = len(matrix)
        C = len(matrix[0])
        
        for i in range(R):
            if matrix[i][0] == 0:
                isCol = True
            for j in range(1, C):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        for j in range(1, C):
            if matrix[0][j] == 0:
                setColZeros(matrix, j)
                
        for i in range(R):
            if matrix[i][0] == 0:
                setRowZeros(matrix, i)
        
        if isCol:
            setColZeros(matrix, 0)

另一种方法是用一个特殊符合标记需要改变的结果,只要这个特殊标记不在我们的题目数据范围(0和1)即可,这里用None。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        这题要解决的问题是,必须有个地方记录判断结果,但又不能影响下一步的判断条件;
        直接改为0的话,会影响下一步的判断条件;
        因此,有一种思路是先改为None,最后再将None改为0;
        从条件上看,如果可以将第一行、第二行作为记录空间,那么,用None应该也不算违背题目条件;
        """
        rows = len(matrix)
        cols = len(matrix[0])
        # 遍历矩阵,用None记录要改的地方,注意如果是0则要保留,否则会影响下一步判断
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] is not None and matrix[r][c] == 0:
                    # 改值
                    for i in range(rows):
                        matrix[i][c] = None if matrix[i][c] != 0 else 0
                    for j in range(cols):
                        matrix[r][j] = None if matrix[r][j] != 0 else 0
        # 再次遍历,将None改为0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] is None:
                    matrix[r][c] = 0

扩展

为什么选择第一行第一列,选择其他行和列可以么?为什么?
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - set-matrix-zeroes - !
文章作者: lonuslan
文章链接: https://louislan.com/articles/2020/02/17/1581907000316.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LouisLan
    评论
    0 评论
avatar

取消