题目描述
给定一个 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) 的额外空间,但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗?
思路:
- 一种直接的解决方案是另开一个同样大小的矩阵,通过扫描原矩阵在新矩阵做赋值。
- 一个简单的改进方案使用O(m + n),可以定义两个数组
一个长度为m,一个长度为n
标记需要置零的行和列。 - 常量级空间的方案是基于第二个方法的改进,我们将矩阵的第一列看成
长度为m-1的数组
,第一行看成长度为n-1的数组
,用它们来标记它们右下角大小为(m - 1) * (n - 1)
的数组需要置零的行和列,这就变成了第二个方法的解法,只需要另外定义两个变量rowFlag
和colFlag
标记第一行和第一列本来有没有含有0
。
匈牙利著名数学家罗莎·彼得在他的名著《无穷的玩艺》中,通过一个十分生动而有趣的笑话,来说明数学家是如何用化归的思想方法来解题的。有人提出了这样一个问题:“假设在你面前有煤气灶,水龙头、水壶和火柴,你想烧开水,应当怎样去做?”对此,某人回答说:“在壶中灌上水,点燃煤气,再把壶放在煤气灶上。”提问者肯定了这一回答,但是,他又追问道:“如果其他的条件都没有变化,只是水壶中已经有了足够的水,那么你又应该怎样去做?”这时被提问者一定会大声而有把握地回答说:“点燃煤气,再把水壶放上去。”但是更完善的回答应该是这样的:“只有物理学家才会按照刚才所说的办法去做,而数学家却会回答:‘只须把水壶中的水倒掉,问题就化归为前面所说的问题了’”。
我们将原矩阵切两刀把右下角大小为(m-1)*(n-1)
的矩阵和第一行、第一列
切出来,就可以使用常量空间而变成了第二种方法的解法,最后对第一行和第一列做下置零处理即可。
class Solution {
//用矩阵的第一行保存需要置零的列,第一列保存需要置零的行
//rowFlag,colFlag分别标记第一行和第一列本来有没有0
public void setZeroes(int[][] matrix) {
boolean rowFlag = false, colFlag = false;
//第一列是否含有0
for(int row = 0; row < matrix.length;row++){
if(matrix[row][0] == 0){
colFlag = true;
break;
}
}
//第一行是否含有0
for(int col = 0; col < matrix[0].length;col++){
if(matrix[0][col] == 0){
rowFlag = true;
break;
}
}
for(int row = 1;row < matrix.length;row++){
for(int col = 1;col < matrix[0].length;col++){
if(matrix[row][col] == 0){
matrix[row][0] = 0;
matrix[0][col] = 0;
}
}
}
//将行置零
for(int row = 1;row < matrix.length;row++){
if(matrix[row][0] == 0){
for(int col = 1;col < matrix[0].length;col++){
matrix[row][col] = 0;
}
}
}
//将列置零
for(int col = 1;col < matrix[0].length;col++){
if(matrix[0][col] == 0){
for(int row = 1;row < matrix.length;row++){
matrix[row][col] = 0;
}
}
}
//第一行置零
if(rowFlag == true){
for(int col = 0;col < matrix[0].length;col++){
matrix[0][col] = 0;
}
}
//第一列置零
if(colFlag == true){
for(int row = 0;row < matrix.length;row++){
matrix[row][0] = 0;
}
}
}
}
网友评论