内容简介:给定一个 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顺时针打印矩阵
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
PHP经典实例(第3版)
David Sklar、Adam Trachtenberg / 苏金国、丁小峰 / 中国电力出版社 / 2015-7 / 128.00
想要掌握PHP编程技术?或者想要学习如何完成一个特定的任务?那么一定要先看看《PHP经典实例(第3版)》。本书介绍了专门为PHP 5.4和5.5修订的350个经典技巧,并提供了丰富的示例代码。特别是对生成动态Web内容的解决方案做了全面更新,从使用基本数据类型到查询数据库,从调用RESTful API到测试和保护网站安全都有涵盖。 各个技巧都提供了示例代码,可以免费使用,另外还讨论了如何解决......一起来看看 《PHP经典实例(第3版)》 这本书的介绍吧!