73.矩阵置零 python

news/2025/1/12 13:21:19/

矩阵置零

  • 题目
    • 题目描述
    • 示例 1:
    • 示例 2:
    • 提示:
  • 题解
    • 思路分析
    • Python 实现代码
    • 代码解释
    • 提交结果

题目

题目描述

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 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
- 2 31 2^{31} 231 <= matrix[i][j] <= 2 31 2^{31} 231 - 1

题解

思路分析

为了在不使用额外空间的情况下完成这个任务,我们可以利用矩阵的第一行和第一列来记录哪些行和列需要被置零。具体步骤如下:

  1. 检查第一行和第一列是否有零:我们需要单独检查第一行和第一列中是否包含零,因为稍后我们会用它们来存储其他行和列的信息。
  2. 标记需要置零的行和列:遍历整个矩阵,当发现某个元素为零时,将该元素所在的行的第一个元素和该元素所在的列的第一个元素设置为零。
  3. 根据标记置零:再次遍历矩阵(从最后一行开始,以避免覆盖第一行和第一列中的标记),如果某一行或某一列的第一个元素为零,则将整行或整列置零。
  4. 处理第一行和第一列:最后,根据第一步的结果决定是否需要将第一行或第一列置零。

Python 实现代码

python">def setZeroes(matrix):m, n = len(matrix), len(matrix[0])# Step 1: Check if the first row and first column contain zerosfirst_row_has_zero = any(matrix[0][j] == 0 for j in range(n))first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))# Step 2: Mark rows and columns that need to be zeroedfor i in range(1, m):for j in range(1, n):if matrix[i][j] == 0:matrix[i][0] = 0matrix[0][j] = 0# Step 3: Set matrix elements to zero based on marksfor i in range(1, m):for j in range(1, n):if matrix[i][0] == 0 or matrix[0][j] == 0:matrix[i][j] = 0# Step 4: Handle first row and columnif first_row_has_zero:for j in range(n):matrix[0][j] = 0if first_col_has_zero:for i in range(m):matrix[i][0] = 0

代码解释

  1. 检查第一行和第一列:通过 any 函数检查第一行和第一列中是否存在零,并保存结果。
  2. 标记需要置零的行和列:遍历矩阵,对于每个为零的元素,将其对应的行首和列首元素也设为零。
  3. 根据标记置零:从矩阵的最后一个元素开始向前遍历,如果某一行或某一列的标志位为零,则将该行或该列的所有元素置零。
  4. 处理第一行和第一列:最后根据第一步的检查结果决定是否需要将第一行或第一列置零。

这种方法确保了我们只使用常数级别的额外空间(O(1)),并且有效地完成了原地算法的要求。

提交结果

在这里插入图片描述


http://www.ppmy.cn/news/1562513.html

相关文章

网络编程的进程查看连接描述符信息等

一.查看当前进程的socket对应的fd信息 1. lsof lsof&#xff08;List Open Files&#xff09;命令可以列出系统中所有打开的文件的信息&#xff0c;包括 socket。 用法 要查看特定进程的 socket 信息&#xff0c;可以使用以下命令&#xff1a; lsof -p <pid> | grep…

如何构建多层决策树

构建一颗多层的决策树时&#xff0c;通过递归选择最佳划分特征&#xff08;依据 信息增益 或 基尼系数&#xff09;对数据集进行划分&#xff0c;直到满足停止条件&#xff08;例如叶节点纯度达到要求或树的深度限制&#xff09;。以下是基于 信息增益 和 基尼系数 的递推公式和…

12工具篇(D2_Commons-lang3)

目录 一、基本介绍 二、commons-lang3库的引用 三、常用工具类 1. StringUtils 2. RandomStringUtils 3. NumberUtils 4. ArrayUtils 5. DateUtils 6. StringUtile 7. BeanUtils 7.1 基本介绍 7.2 JavaBean 7.3 两个概念 7.4 常用操作 7.5 应用 1. JavaBean 的属…

ISP架构方案

外置 ISP 架构 外置 ISP 架构是指在 AP 外部单独布置 ISP 芯片用于图像信号处理。外置 ISP 的架构图一般如下所示&#xff1a; 外置 ISP 架构的优点主要有&#xff1a; 能够提供更优秀的图像质量&#xff1a;在激烈的市场竞争下&#xff0c;能够存活到现在的外置 ISP 生产厂商在…

飞书二维码登录注意点

1.前端SDK版本 第一个手机端授权后、网页端还需要点击一次授权 授权后会跳转到redirect_uri页面&#xff0c;连接会携带code<script src"https://lf-package-cn.feishucdn.com/obj/feishu-static/lark/passport/qrcode/LarkSSOSDKWebQRCode-1.0.3.js"></scr…

k8s之pod生命周期

一.pod生命周期:pod对象从创建开始到终止的过程1.作用:复杂服务的启动顺序,依赖关系,容器服务启动前的相关操作,配置文件生成,依赖服务检测等...2.生命周期流程:初始化容器--主容器--启动后回调函数-->启动,生命,就绪探针-->关闭前回调函数初始化容器执行&#xff1a;执行…

istio-proxy内存指标

在 Istio 环境中&#xff0c;istio-proxy 是 Envoy 的边车代理容器。通过运行命令 curl localhost:15000/memory&#xff0c;或者curl localhost:15000/stats 可以查询 Envoy 的内存统计信息。以下是典型返回结果的结构和意义&#xff1a; 返回结果单位是bytes&#xff0c;需/…

PHP与ThinkPHP连接数据库示例

【图书介绍】《ThinkPHP 8高效构建Web应用》-CSDN博客 《2025新书 ThinkPHP 8高效构建Web应用 编程与应用开发丛书 夏磊 清华大学出版社教材书籍 9787302678236 ThinkPHP 8高效构建Web应用》【摘要 书评 试读】- 京东图书 使用VS Code开发ThinkPHP项目-CSDN博客 编程与应用开…