作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、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] ]
方法一：使用额外存储空间
解题步骤
- 标记零的位置：遍历整个矩阵，使用两个集合来分别记录哪些行和哪些列需要被置零。
- 置零行和列：再次遍历矩阵，根据行和列的集合来置零对应的行和列。
完整的规范代码
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))，使用了额外空间来存储需要置零的行和列。
方法二：使用常数空间的优化
解题步骤
- 原地修改：使用矩阵的第一行和第一列来记录该行或列是否需要置零。
- 单独标记第一行和第一列：因为第一行和第一列共用 matrix[0][0]，所以需要一个额外的标记来区分第一列是否需要置零。
- 二次遍历填充：第一次从底部开始遍历以避免提前修改第一行或第一列的值，第二次从顶部开始正常遍历并使用第一行和第一列的标记来置零。
完整的规范代码
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))，除了几个用于标记的变量外，没有使用额外的空间。
方法三：改进的标记方法
解题步骤
- 单次遍历：在第一次遍历的同时，直接在第一行和第一列上进行标记。
- 尾部处理：利用第一行和第一列的标记进行最后的置零处理。
完整的规范代码
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))，使用了原矩阵的第一行和第一列作为标记，没有额外空间。
方法四：首尾标记优化
解题步骤
- 首尾行列标记：分别使用矩阵的首行和尾行进行置零标记。
- 中间处理：根据首尾标记决定中间行列是否需要置零。
完整的规范代码
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))，使用首尾行列作为标记，不需要额外空间。
方法五：位运算标记法
解题步骤
- 使用位运算标记：通过位运算标记哪些行和列需要置零。
- 处理置零：根据标记，决定如何置零矩阵中的行和列。
完整的规范代码
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)) |
| 优势 | 简单直观 | 空间高效 | 一次遍历即可 | 特殊行列单独处理 | 位操作快速且节省空间 |
| 劣势 | 空间占用较大 | 需要复杂的标记逻辑 | 实现稍复杂 | 实现稍复杂 | 对位操作要求较高，可能增加实现复杂性 |
应用示例
图像处理：在图像处理中，可能需要对图像矩阵进行操作，类似于置零的操作可用于快速清除某些区域。
数据清洗：在数据预处理阶段，需要将包含无效数据的行和列清除，这些算法可直接应用于清洗包含缺失值的数据集。
软件开发：在软件开发中，处理大规模数据时常需要类似的矩阵操作来快速应用某些条件，这些方法提供了多种实现这一功能的方式。
欢迎关注微信公众号 数据分析螺丝钉
