【Set Matrix Zeros】cpp
2024-09-04 11:39:48
题目：
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
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?
代码：
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
const size_t size_row = matrix.size();
const size_t size_col = matrix[].size();
bool if_row0_has_zero = false;
bool if_col0_has_zero = false;
for (size_t col = ; col < size_col; ++col){
if (matrix[][col]==){
if_row0_has_zero = true;
break;
}
}
for (size_t row = ; row < size_row; ++row){
if (matrix[row][]==){
if_col0_has_zero = true;
break;
}
}
for (size_t row = ; row < size_row; ++row){
for (size_t col = ; col < size_col; ++col){
if (matrix[row][col]==){
matrix[row][] = ;
matrix[][col] = ;
}
}
}
for (size_t row = ; row < size_row; ++row){
for (size_t col = ; col < size_col; ++col){
if ( matrix[row][]== || matrix[][col]== ) matrix[row][col]=;
}
}
if (if_row0_has_zero) {
for (size_t col = ; col < size_col; ++col) matrix[][col]=;
}
if (if_col0_has_zero){
for (size_t row = ; row < size_row; ++row) matrix[row][]=;
}
}
};
Tips:
1. 算法时间复杂度上是O(n²)
2. 这里为了节省空间复杂度，用到的技巧是把第一行和第一列作为该行或该列是否含有0元素的标志位，这样就可以在常数空间内完成题目。
========================================================
第二次过这道题，思路比较清晰，代码也一次AC了。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size()==) return;
// check first row
bool first_row_zero = false;
for ( int j=; j<matrix[].size(); ++j ) {
if (matrix[][j]==) {first_row_zero=true;break;}
}
// check frist col
bool first_col_zero = false;
for ( int j=; j<matrix.size(); ++j ) {
if ( matrix[j][]==) {first_col_zero=true;break;}
}
// check remains
for ( int i=; i<matrix.size(); ++i )
{
for ( int j=; j<matrix[i].size(); ++j )
{
if ( matrix[i][j]== )
{
matrix[][j] = ;
matrix[i][] = ;
}
}
}
// set row zeros
for ( int i=; i<matrix.size(); ++i )
{
if ( matrix[i][]== )
{
for ( int j=; j<matrix[i].size(); ++j ) matrix[i][j] = ;
}
}
// set col zeros
for ( int j=; j<matrix[].size(); ++j )
{
if ( matrix[][j]== )
{
for ( int i=; i<matrix.size(); ++i ) matrix[i][j] = ;
}
}
if (first_row_zero)
{
for ( int j=; j<matrix[].size(); ++j ) matrix[][j] = ;
}
if ( first_col_zero)
{
for ( int i=; i<matrix.size(); ++i ) matrix[i][] = ;
}
}
};
这个代码大体上没有问题，但是在一个部分是可以优化的。就是set row zeros和set col zeros两个部分可以合成一个，改一版代码如下。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size()==) return;
// check first row
bool first_row_zero = false;
for ( int j=; j<matrix[].size(); ++j ) {
if (matrix[][j]==) {first_row_zero=true;break;}
}
// check frist col
bool first_col_zero = false;
for ( int j=; j<matrix.size(); ++j ) {
if ( matrix[j][]==) {first_col_zero=true;break;}
}
// check remains
for ( int i=; i<matrix.size(); ++i )
{
for ( int j=; j<matrix[i].size(); ++j )
{
if ( matrix[i][j]== )
{
matrix[][j] = ;
matrix[i][] = ;
}
}
}
// set zeros
for ( int i=; i<matrix.size(); ++i )
{
for ( int j=; j<matrix[i].size(); ++j )
{
if ( matrix[i][]== || matrix[][j]== ) matrix[i][j]=;
}
}
if (first_row_zero)
{
for ( int j=; j<matrix[].size(); ++j ) matrix[][j] = ;
}
if ( first_col_zero)
{
for ( int i=; i<matrix.size(); ++i ) matrix[i][] = ;
}
}
};
这样改版后，代码效率提升了。
最新文章
- Core functionality.md
- struts2学习记录
- ios 控件显示不出来的几个可能
- Rainyday.js – 使用 JavaScript 实现雨滴效果
- SQLServer中的事务与锁
- 关于主机FTP连接不上,无法列出目录,列表错误,上传速度慢,掉速的解决办法
- SQLServer的数据类型
- git初识
- C++11实现Qt的信号槽机制
- T-SQL 一次插入多行数据
- android微信付费
- SpringMVC初步——HelloWorld的实现
- js-轮播图
- java 数据设置和显示
- tab面板，html+css
- linux查看日志文件内容命令tail、cat、tac、head、echo
- require/exports 和 import/export 区别
- 理解 RxJava 的线程模型
- day05 模块学习
- 10. 面向holder编程、自动轮询