【LeetCode】Set Matrix Zeroes 解题报告
2024-10-19 01:18:30
今天看到CSDN博客的勋章换了图表,同一时候也添加显示了博客等级,看起来都听清新的,感觉不错!
【题目】
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?
【思路】
我直接看了以下的要求,最先想到的就是O(m+n)的空间,就是加一行一列来标记哪行哪列有0;反而是O(mn)的空间不知该怎么利用了。
接下来想O(1)空间,略微一想,居然想到了答案,就是相比用O(m+n)的空间,不额外加一行一列,就用第一行和第一列来存储哪行哪列有0。当然,这样做比較麻烦的是第一行第一列的原始信息,须要先保存下来。
前两次写的时候,因为第一行第一列没有处理好,导致WA。
AC后看网上答案,看到其它人也是这么一个思路,挺高兴的。
【Java代码,O(1)空间】
public class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int i, j; //先标记第一行和第一列是否有0
boolean firstRow = false, firstCol = false;
for (j = 0; j < n; j++) {
if (0 == matrix[0][j]) {
firstRow = true;
break;
}
}
for (i = 0; i < m; i++) {
if (0 == matrix[i][0]) {
firstCol = true;
break;
}
} //从第二行第二列还是遍历,假设遇到0,则把它所在行和列的第一个值设为0
for (i = 1; i < m; i++) {
for (j = 1; j < n; j++) {
if (0 == matrix[i][j]) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
} //把第一列的0所在行都设为0,把第一行的0所在列都设为0
for (i = 1; i < m; i++) {
if (0 == matrix[i][0]) {
for (j = 1; j < n; j++) {
matrix[i][j] = 0;
}
}
}
for (j = 1; j < n; j++) {
if (0 == matrix[0][j]) {
for (i = 1; i < m; i++) {
matrix[i][j] = 0;
}
}
} //依据标记决定第一行和第一列是否全设为0
if (firstRow) {
for (j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (firstCol) {
for (i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}
最新文章
- 《Hive编程指南》—— 读后总结
- 商业信息管理系统 Bizagi 建模pattern
- 增值税&mdash;&mdash;基础知识
- excel导入导出
- HDU2648:Shopping(DKBR_hash)
- spring整合quartz实现定时任务
- paip. mysql如何临时 暂时 禁用 关闭 触发器
- Maven镜像配置
- [shell]Shell经常使用特殊符号
- 解決 centos中-bash: vim: command not found
- 转Android 用Animation-list实现逐帧动画
- vscode使用shell
- Android ImgView属性
- 【译】《C# Tips -- Write Better C#》
- (5)Maven快速入门_5maven聚合与继承_scope依赖范围
- js 表达式与语句
- centos7使用kubeadm配置高可用k8s集群
- VMware14 安装CentOS7及其配置;CentOS7配置网桥,做远程连接;
- HCNP学习笔记之IP地址、子网掩码、网关的关系
- SQL Server 将Id相同的字段合并,并且以逗号隔开