题目地址
https://leetcode.com/problems/set-matrix-zeroes/description/
题目描述
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?
思路
符合直觉的想法是,使用一个 m + n 的数组来表示每一行每一列是否”全部是 0“,
先遍历一遍去构建这样的 m + n 数组,然后根据这个 m + n 数组去修改 matrix 即可。
这样的时间复杂度 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“去更新第一行和第一列即可
关键点
- 使用第一行和第一列来替代我们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
扩展
为什么选择第一行第一列,选择其他行和列可以么?为什么?
LeetCode题解240.search-a-2-d-matrix-ii题目地址 https://leetcode.com/problems/search-a-2d-matrix-ii/description/ 题目描述 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following …
LeetCode题解378.kth-smallest-element-in-a-sorted-matrix题目地址 https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/ 题目描述 Given a n x n matrix where each of the rows and columns are sorted in ascending order, …
LeetCode题解172.factorial-trailing-zeroes题目地址 https://leetcode.com/problems/factorial-trailing-zeroes/description/ 题目描述 Given an integer n, return the number of trailing zeroes in n!. Example 1: Input: 3 Output: 0 Explana…
LeetCode题解283.move-zeroes题目地址 https://leetcode.com/problems/move-zeroes/description/ 题目描述 Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the …
循环外的临时数组的空间复杂度 - java我确实遇到了一个著名的面试问题,其中给了我们2D数组,我们需要将数组旋转90度,尽管有很多方法可以解决它,但我决定采用一种有效的方法这样的事情。/* * clockwise rotate * first reverse up to down, then swap the symmetry * 1 2 3 7 8 9 7 4 1 * 4 5 6 => 4…