LeetCode题目73:矩阵置零

简介: LeetCode题目73:矩阵置零

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

输入格式
  • matrix:一个二维整数数组。
输出格式
  • 不返回任何内容,但要将 matrix 中的行和列置零。

示例

示例 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]
]

方法一:使用额外存储空间

解题步骤
  1. 标记零的位置:遍历整个矩阵,使用两个集合来分别记录哪些行和哪些列需要被置零。
  2. 置零行和列:再次遍历矩阵,根据行和列的集合来置零对应的行和列。
完整的规范代码
def setZeroes(matrix):
    """
    使用额外存储空间的方法来置零矩阵
    :param matrix: List[List[int]], 输入的二维矩阵
    """
    rows, cols = set(), set()
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                rows.add(i)
                cols.add(j)
    for i in range(m):
        for j in range(n):
            if i in rows or j in cols:
                matrix[i][j] = 0
# 示例调用
matrix = [
    [1,1,1],
    [1,0,1],
    [1,1,1]
]
setZeroes(matrix)
print(matrix)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
算法分析
  • 时间复杂度:(O(m * n)),需要两次遍历整个矩阵。
  • 空间复杂度:(O(m + n)),使用了额外空间来存储需要置零的行和列。

方法二:使用常数空间的优化

解题步骤
  1. 原地修改:使用矩阵的第一行和第一列来记录该行或列是否需要置零。
  2. 单独标记第一行和第一列:因为第一行和第一列共用 matrix[0][0],所以需要一个额外的标记来区分第一列是否需要置零。
  3. 二次遍历填充:第一次从底部开始遍历以避免提前修改第一行或第一列的值,第二次从顶部开始正常遍历并使用第一行和第一列的标记来置零。
完整的规范代码
def setZeroes(matrix):
    """
    使用常数空间的方法来置零矩阵
    :param matrix: List[List[int]], 输入的二维矩阵
    """
    m, n = len(matrix), len(matrix[0])
    first_col = any(matrix[i][0] == 0 for i in range(m))
    for i in range(m):
        for j in range(1, n):  # 从第二列开始
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    for i in range(m - 1, -1, -1):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
        if first_col:
            matrix[i][0] = 0
# 示例调用
matrix = [
    [0,1,2,0],
    [3,4,5,2],
    [1,3,1,5]
]
setZeroes(matrix)
print(matrix)  # 输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
算法分析
  • 时间复杂度:(O(m * n)),两次遍历整个矩阵。
  • 空间复杂度:(O(1)),除了几个用于标记的变量外,没有使用额外的空间。

方法三:改进的标记方法

解题步骤
  1. 单次遍历:在第一次遍历的同时,直接在第一行和第一列上进行标记。
  2. 尾部处理:利用第一行和第一列的标记进行最后的置零处理。
完整的规范代码
def setZeroes(matrix):
    """
    改进的标记方法来置零矩阵
    :param matrix: List[List[int]], 输入的二维矩阵
    """
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        if matrix[i][0] == 0:
            first_col_zero = True
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, 0, -1):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
        if first_col_zero:
            matrix[i][0] = 0
# 示例调用
matrix = [
    [1,1,1],
    [1,0,1],
    [1,1,1]
]
setZeroes(matrix)
print(matrix)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
算法分析
  • 时间复杂度:(O(m * n)),只有一次遍历,但每个元素都被检查。
  • 空间复杂度:(O(1)),使用了原矩阵的第一行和第一列作为标记,没有额外空间。

方法四:首尾标记优化

解题步骤
  1. 首尾行列标记:分别使用矩阵的首行和尾行进行置零标记。
  2. 中间处理:根据首尾标记决定中间行列是否需要置零。
完整的规范代码
def setZeroes(matrix):
    """
    首尾标记优化方法来置零矩阵
    :param matrix: List[List[int]], 输入的二维矩阵
    """
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    last_row_zero = any(matrix[m-1][j] == 0 for j in range(n))
    for i in range(1, m-1):
        for j in range(1, n-1):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    for i in range(1, m-1):
        for j in range(1, n-1):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if last_row_zero:
        for j in range(n):
            matrix[m-1][j] = 0
# 示例调用
matrix = [
    [1,1,1],
    [1,0,1],
    [1,1,1]
]
setZeroes(matrix)
print(matrix)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
算法分析
  • 时间复杂度:(O(m * n)),通过两次遍历完成。
  • 空间复杂度:(O(1)),使用首尾行列作为标记,不需要额外空间。

方法五:位运算标记法

解题步骤
  1. 使用位运算标记:通过位运算标记哪些行和列需要置零。
  2. 处理置零:根据标记,决定如何置零矩阵中的行和列。
完整的规范代码
def setZeroes(matrix):
    """
    位运算标记法来置零矩阵
    :param matrix: List[List[int]], 输入的二维矩阵
    """
    row_flag, col_flag = 0, 0
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                row_flag |= (1 << i)
                col_flag |= (1 << j)
    for i in range(m):
        for j in range(n):
            if row_flag & (1 << i) or col_flag & (1 << j):
                matrix[i][j] = 0
# 示例调用
matrix = [
    [1,1,1],
    [1,0,1],
    [1,1,1]
]
setZeroes(matrix)
print(matrix)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
算法分析
  • 时间复杂度:(O(m * n)),必须遍历整个矩阵来标记和处理。
  • 空间复杂度:(O(1)),使用固定数量的位标记。

不同算法的优劣势对比

特征 方法一:额外存储 方法二:常数空间优化 方法三:改进标记 方法四:首尾标记优化 方法五:位运算标记
时间复杂度 (O(m * n)) (O(m * n)) (O(m * n)) (O(m * n)) (O(m * n))
空间复杂度 (O(m + n)) (O(1)) (O(1)) (O(1)) (O(1))
优势 简单直观 空间高效 一次遍历即可 特殊行列单独处理 位操作快速且节省空间
劣势 空间占用较大 需要复杂的标记逻辑 实现稍复杂 实现稍复杂 对位操作要求较高,可能增加实现复杂性

应用示例

图像处理:在图像处理中,可能需要对图像矩阵进行操作,类似于置零的操作可用于快速清除某些区域。

数据清洗:在数据预处理阶段,需要将包含无效数据的行和列清除,这些算法可直接应用于清洗包含缺失值的数据集。

软件开发:在软件开发中,处理大规模数据时常需要类似的矩阵操作来快速应用某些条件,这些方法提供了多种实现这一功能的方式。

欢迎关注微信公众号 数据分析螺丝钉


相关文章
|
2月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
6天前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
2月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
39 6
|
2月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
24 4
|
2月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
19 0
【Leetcode刷题Python】73. 矩阵置零
|
2月前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。
|
4月前
|
算法
力扣经典150题第三十七题:矩阵置零
力扣经典150题第三十七题:矩阵置零
27 2
|
4月前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
27 1
|
3月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)