力扣每日一题73:矩阵置零

题目描述:

给定一个 m x n 的矩阵,如果一个元素为 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

示例 1:

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:

输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

进阶:

  • 一个直观的解决方案是使用  O(mn) 的额外空间,但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗?

通过次数

286.9K

提交次数

446.4K

通过率

64.3%

思路和题解:

一、先遍历一次矩阵,用一个数组row和一个数组col标记要置零的行和列,随后再遍历一次矩阵,如果矩阵所在行或列要置0,那就变零。时间复杂度O(m*n),空间复杂度O(m+n)

代码:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        //记录要置零的行和列
        vector<int> row(m,0);
        vector<int> col(n,0);
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(matrix[i][j]==0)
                    row[i]=col[j]=1;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(row[i]==1||col[j]==1)
                    matrix[i][j]=0;
    }
};

二、方法一的改进,矩阵的第一行和第一列代替col和row,实现O(1)空间复杂度,但矩阵的第一行和第一列有交叉,交叉的位置既要标记第一行是否出现零,又要标记第一列是否出现零,所以我们应该额外设置一个变量flag,flag与matrix[0][0]一个标记第一行是否出现零,一个标记第一列是否出现零。

代码:

lass Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        bool flag_col0=false;
        //标记
        for(int i=0;i<m;i++)
        {
            if(matrix[i][0]==0) flag_col0=true;
            for(int j=1;j<n;j++)
            {
                if(matrix[i][j]==0)
                    matrix[i][0]=matrix[0][j]=0;
            }
        }
        // 置零
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[i][0]==0||matrix[0][j]==0)
                    matrix[i][j]=0;
            }
        }
        if(matrix[0][0]==0)
            for(int j=0;j<n;j++) matrix[0][j]=0;
        if(flag_col0==true)
            for(int j=0;j<m;j++) matrix[j][0]=0;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/108332.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Unable to find GatewayFilterFactory with name TokenRelay

目录 问题分析解决方案参考文档开源项目微服务商城项目前后端分离项目 问题分析 Spring Cloud Gateway 网关作为代理资源服务器&#xff0c;需要将 JWT 传递给下游资源服务器&#xff0c;下面是网关的配置 spring:cloud:gateway:discovery:locator:enabled: true # 启用服务发…

Rabbitmq----分布式场景下的应用

服务异步通信-分布式场景下的应用 如果单机模式忘记也可以看看这个快速回顾rabbitmq,在做学习 消息队列在使用过程中&#xff0c;面临着很多实际问题需要思考&#xff1a; 1.消息可靠性 消息从发送&#xff0c;到消费者接收&#xff0c;会经理多个过程&#xff1a; 其中的每一…

【Qt之QSetting】介绍及使用

概述 QSettings类提供了一种持久的、与平台无关的应用程序设置存储功能。 用户通常期望一个应用能在不同会话中记住其设置&#xff08;窗口大小和位置&#xff0c;选项等&#xff09;。在Windows上&#xff0c;这些信息通常存储在系统注册表中&#xff1b;在macOS和iOS上&…

通过阿里云创建accessKeyId和accessKeySecret

我们想实现服务端向个人发送短信验证码 需要通过accessKeyId和accessKeySecret 这里可以白嫖阿里云的 这里 我们先访问阿里云官网 阿里云地址 进入后搜索并进入短信服务 如果没登录 就 登录一下先 然后在搜索框搜索短信服务 点击进入 因为我也是第一次操作 我们一起点免费开…

《算法通关村—计算器|逆波兰问题解析》

《算法通关村—计算器|逆波兰问题解析》 计算器问题 描述 LeetCode227.给你一个字符串表达式 s &#xff0c;请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。 输入&#xff1a;s "32*2" 输出&#xff1a;7基本思路&#xff1a;理解题目&a…

响应式相册写真摄影网站模板源码

模板信息&#xff1a; 模板编号&#xff1a;28526 模板编码&#xff1a;UTF8 模板颜色&#xff1a;黑白 模板分类&#xff1a;摄像、婚庆、家政、保洁 适合行业&#xff1a;婚纱摄影类企业 模板介绍&#xff1a; 本模板自带eyoucms内核&#xff0c;无需再下载eyou系统&#x…

【SPSS】基于RFM+Kmeans聚类的客户分群分析(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

精讲双向链表的销毁

相信大家各位学习双向链表的时候对链表的销毁&#xff0c;都或多或少有些小疑惑&#xff0c;我到底是传一级指针还是传二级指针 木关系&#xff0c;这些都是小意思&#xff0c;今天我将为大家share 一下关于到底如何进行正确传指针 对于链表是销毁其实就是对链表进行一个结点一…

Qt配置OpenCV教程,亲测已试过

详细版可参考&#xff1a;Qt配置OpenCV教程&#xff0c;亲测已试过&#xff08;详细版&#xff09;_qt opencv_-_Matrix_-的博客-CSDN博客 软件准备&#xff1a;QtOpenCVCMake (QtOpenCV安装不说了&#xff0c;CMake的安装&#xff0c;我用的是&#xff1a;可参考博客&#x…

Java集成腾讯云OCR身份证识别接口

一、背景 项目用到身份证识别获取人员信息的功能&#xff0c;于是想到了腾讯云提供这样的API。在整合代码过程都很顺利&#xff0c;利用腾讯云官方SDK很快集成进来。但是在上测试环境部署时有了新的问题&#xff0c;通过Nginx代理后的环境无法访问到目标腾讯云接口&#xff0c;…

云起无垠典型案例入选《2023软件供应链安全洞察》报告

近日&#xff0c;历时6个月&#xff0c;由ISC编制的《2023软件供应链安全洞察》报告&#xff08;以下简称《报告》&#xff09;正式对外发布。《报告》围绕软件供应链安全现状、技术内核、治理指南、落地实践展开&#xff0c;以期为行业从业者提供有价值的信息和洞见&#xff0…

飞利浦双串口51单片机485网关

主要功能将PC端的数据接收下来&#xff0c;分发到不同的设备&#xff0c;也是轮询设备数据读取回来&#xff0c;打包回传到PC端&#xff0c;数据包包头包尾识别&#xff0c;数据校验&#xff0c;接收超时处理&#xff0c;将协议结构化处理&#xff0c;协议的改动不需要改动程序…

Python学习笔记--初始化函数

六、初始化函数 1、什么是初始化函数 初始化函数的意思是&#xff0c;当你创建一个实例的时候&#xff0c;这个函数就会被调用。 比如&#xff1a; 当代码在执行 a ClassA() 的语句时&#xff0c;就自动调用了 __init__(self) 函数。 而这个 __init__(self) 函数就是初始化…

为什么数组的下标是从0开始呢?

我们在许多的编程语言中&#xff0c;大部分的数组下标都是从零开始的&#xff0c;那为什么不是从一开始的呢&#xff1f; 首先我们&#xff0c;先要了解数组相关的定义。 数组&#xff08;Array&#xff09;是一种线性表数据结构。它用一组连续的内存空间&#xff0c;来存储一…

【Linux】虚拟机安装Linux、客户端工具及Linux常用命令(详细教程)

目录 一、导言 1、引言 2、使用场景 二、Linux安装 1、安装 2、网络配置 2.1、查看网络配置 2.2、更改网络配置 三、安装客户端工具 1、介绍 2、安装MobaXterm 3、换源 4、拍照功能 四、常用命令 一、导言 1、引言 Linux是一个开源的操作系统内核&#xff0c;它最…

粤嵌实训医疗项目--day03(Vue + SpringBoot)

往期回顾 粤嵌实训医疗项目day02&#xff08;Vue SpringBoot&#xff09;-CSDN博客 粤嵌实训医疗项目--day01&#xff08;VueSpringBoot&#xff09;-CSDN博客 目录 一、SpringBoot AOP的使用 二、用户模块-注册功能&#xff08;文件上传&#xff09; 三、用户模块-注册实现…

【SpringBoot】Docker部署

docker部署是主流的部署方式&#xff0c;极大的方便了开发部署环境&#xff0c;保持了环境的统一&#xff0c;也是实现自动化部署的前提。 1 项目的目录结构 package: 点击打包&#xff0c;生成 xxx-SNAPSHOT.jar target目录: 打包生成目录&#xff0c;生成的jar存放位置Docke…

D-Nerf:用于动态场景表示的神经辐射场

Pumarola A, Corona E, Pons-Moll G, et al. D-nerf: Neural radiance fields for dynamic scenes[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021: 10318-10327. D-Nerf 较 NeRF 的改进 1 就是能够建模移动或变形的物体&#…

分享个包含各省、市、区的编码数据的在线静态资源脚本

在翻《SpringBootVue3》——十三尼克陈作者的大型前后端分离项目实战里面&#xff0c;在看到地址管理的部分时&#xff0c;发现了该作者记录有一个静态的地址资源脚本 这里做个记录&#xff0c;打点 一、引入js <script src"https://s.yezgea02.com/1641120061385/td…

python opencv之图像分割、计算面积

以下代码是一个基于K-means聚类算法进行图像分割的实现。通过读取一个彩色图像&#xff0c;将其转化为二维数组形式。然后使用K-means算法对像素点进行聚类&#xff0c;聚类个数为7。根据聚类后的标签值对像素点进行着色&#xff0c;并创建掩膜图像。接着使用形态学开运算和闭运…