欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 养生 > 73.矩阵置零 python

73.矩阵置零 python

2025/1/20 20:37:40 来源:https://blog.csdn.net/sysu63/article/details/145048375  浏览:    关键词:73.矩阵置零 python

矩阵置零

  • 题目
    • 题目描述
    • 示例 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 实现代码

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)),并且有效地完成了原地算法的要求。

提交结果

在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com