内容简介:给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。示例 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) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗?
思路:利用第一行和第一列记录这一行/列有没有0即可。
(但是要特殊照顾第一行和第一列)
class Solution { public void setZeroes(int[][] matrix) { int row = matrix.length; int col = matrix[0].length; boolean row0_flag = false; boolean col0_flag = false; // 第一行是否有零 for (int j = 0; j < col; j++) { if (matrix[0][j] == 0) { row0_flag = true; break; } } // 第一列是否有零 for (int i = 0; i < row; i++) { if (matrix[i][0] == 0) { col0_flag = true; break; } } // 把第一行第一列作为标志位 for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { if (matrix[i][j] == 0) { matrix[i][0] = matrix[0][j] = 0; } } } // 置0 for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (row0_flag) { for (int j = 0; j < col; j++) { matrix[0][j] = 0; } } if (col0_flag) { for (int i = 0; i < row; i++) { matrix[i][0] = 0; } } } }
以上所述就是小编给大家介绍的《leetcode 73. 矩阵置零》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 机器学习 | SVD矩阵分解算法,对矩阵做拆分,然后呢?
- golang 算法-矩阵
- 彻底理解矩阵乘法
- [开源项目]矩阵数据的意义
- iphone – :CGAffineTransformInvert:奇异矩阵
- golang顺时针打印矩阵
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
从“为什么”开始
[美] 西蒙·斯涅克 / 苏西 / 海天出版社 / 2011-7 / 32.00元
影响人类的行为:要么靠操纵,要么靠感召。 操纵带来的是交易,是短期效益; 感召带来的是信任,是永续经营! 盖茨走后,微软面临怎样的挑战?后盖茨时代,微软为何从一个希望改变世界的公司沦落为一个做软件的公司? 沃尔玛的灵魂人物过世后,一度被人们热爱的公司,遭到的竟然多是顾客、员工的反感?沃尔玛要怎样做才能重放昔日光彩? 星巴克吸引人们购买的不是咖啡,而是理念?为什么说霍华......一起来看看 《从“为什么”开始》 这本书的介绍吧!
Markdown 在线编辑器
Markdown 在线编辑器
HSV CMYK 转换工具
HSV CMYK互换工具