1. 题目描述
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
- 一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗
1. 解题思路
方法一:
最直接的思路就是申请额外的空间去储存0元素所在的行号和列号。
我们需要申请O(m + n)的额外空间,声明两个数组,所占空间分别为m, n。分别用来存放水平方向、竖直方向需要置零的元素下标。
首先先遍历一遍数组,将需要重置的行号和列号存储在数组m和n中。之后再遍历一次原数组,将需要置零的元素置为0。
注意:fill()
方法用于将一个固定值替换数组的元素。语法:array.fill(value, start, end)
,其有三个参数:
- value 必需。填充的值。
- start 可选。开始填充位置。
- end 可选。停止填充位置 (默认为 array.length)
这种方法实现的时间复杂度为O(mn),空间复杂度为O(m + n)
方法二:**
题目上说了能否用常数空间来解决,那就来尝试一下常数空间解决此问题。
如果想要常数空间,就需要再原数组进行操作,我们可以在数组的第一行和第一类在做标记,最后再根据第一行第一列的标记对数组进行置零操作。
大致过程如下:
- 首先从左到右,从上到下遍历数组中每一个元素(列遍历从第二列开始),若该元素为 0,则同时设置该行首列元素、首行该列元素为 0,若首列存在为 0 元素,则设置标识,意为首列元素会被全部置零,此目的是区分行元素与首列元素置零的标识,
- 然后,从右到左,从下到上遍历数组,若首行该列或该行首列元素为 0,则置该元素为 0,若存在标识,则置首列元素为 0,为什么不选择从左到右,从上到下遍历?是因为首行首列的先根据标志置零,新的零元素会影响后面的数据。
这种方法实现的时间复杂度为O(m n),空间复杂度为O(1)**
3. 代码实现
方法一:
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const len = matrix.length // 高
const width = matrix[0].length // 宽
const m = [] // 记录为0的列
const n = [] // 记录为0的行
for(let i = 0; i< len; i++){
for(let j = 0; j < width; j++){
if(!matrix[i][j]){
m.push(j)
n.push(i)
}
}
}
for(let i = 0; i < len; i++){
if(n.indexOf(i) > -1){
matrix[i].fill(0,0,width) // 将有0的行,全部换为为0
}
for(let j = 0; j < m.length; j++){
matrix[i][m[j]] = 0 // 将有0的列,全部换为0
}
}
};
方法二:
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const len = matrix.length // 高
const width = matrix[0].length // 宽
let flag = false
for(let i = 0; i< len; i++){
if(!matrix[i][0]){
flag = true
}
for(let j = 1; j < width; j++){
if(!matrix[i][j]){
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for(let i = len - 1; i >= 0; i--){
for(let j = width - 1; j > 0; j--){
if(!matrix[i][0] || !matrix[0][j]){
matrix[i][j] = 0
}
}
if(flag){
matrix[i][0] = 0
}
}
};
4. 提交结果
方法一:
方法二: