冠军资讯
代码一只喵在面试中，矩阵置零问题经常出现。简单来说，如果一个矩阵中某个元素为 0，则将其所在的行和列的所有元素置为 0。这看似简单，但在追求更高效率和更少空间复杂度的解决方案时，却蕴含着丰富的算法知识和工程实践经验。今天，我们就来深入探讨这个问题，并分享一些实战中的避坑经验。
问题场景重现
给定一个 m x n 的矩阵，如果一个元素是 0，则将其所在行和列的所有元素都设为 0。
例如：
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
底层原理深度剖析
最直观的解法是使用额外的空间来记录哪些行和列需要置零。例如，我们可以使用两个集合，一个存储需要置零的行，一个存储需要置零的列。然后，遍历矩阵，根据这两个集合来置零。这种方法的时间复杂度是 O(m*n)，空间复杂度是 O(m+n)。
能否进一步优化空间复杂度呢？答案是肯定的。我们可以使用矩阵的第一行和第一列来记录哪些行和列需要置零。但需要注意的是，如果第一行或第一列本身就包含 0，那么我们需要额外的变量来记录这种情况。否则，第一行和第一列的所有元素都会被置零，导致错误的结果。
这种优化后的方法的时间复杂度仍然是 O(m*n)，但空间复杂度降低到了 O(1)。这在嵌入式开发或者对内存资源敏感的场景下非常重要。 类似于在 Nginx 配置中， 优化 access_log 可以减少磁盘 IO，提高性能。
具体的代码解决方案
下面是使用 Python 实现的 O(1) 空间复杂度的矩阵置零算法：
def set_matrix_zero(matrix):
"""矩阵置零，空间复杂度 O(1)"""
m = len(matrix)
n = len(matrix[0]) if m > 0 else 0
first_row_has_zero = False
first_col_has_zero = False
# 检查第一行是否包含 0
for j in range(n):
if matrix[0][j] == 0:
first_row_has_zero = True
break
# 检查第一列是否包含 0
for i in range(m):
if matrix[i][0] == 0:
first_col_has_zero = True
break
# 使用第一行和第一列作为标记
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# 根据第一行和第一列的标记置零
for 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
# 处理第一行
if first_row_has_zero:
for j in range(n):
matrix[0][j] = 0
# 处理第一列
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0
return matrix
# 示例
matrix = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
result = set_matrix_zero(matrix)
print(result)
实战避坑经验总结
- 空矩阵处理：在实际应用中，需要考虑矩阵为空的情况。在上面的代码中，我们首先判断了
m > 0，避免了空矩阵导致的错误。 - 原地修改：矩阵置零要求原地修改矩阵。这意味着我们不能创建新的矩阵，而是直接修改原始矩阵。如果在大型系统中，涉及到大量数据处理，要小心数据竞争问题， 适当使用锁机制，或者采用 Copy-on-Write 技术。
- 第一行/列冲突：使用第一行和第一列作为标记位时，需要特别注意第一行和第一列本身包含 0 的情况。否则，会导致错误的结果。我们使用
first_row_has_zero和first_col_has_zero变量来处理这种情况。 - 数据类型：确保矩阵中的元素是可修改的。例如，如果矩阵中的元素是不可变类型（例如
tuple），则无法原地修改。 - 性能优化：虽然 O(1) 空间复杂度已经很优秀，但在某些情况下，如果矩阵非常大，且 0 的分布非常稀疏，那么使用额外的空间来加速算法可能更有效。这需要在实际应用中进行权衡。
拓展思考
矩阵置零问题可以拓展到更高维度的数组。例如，如果给定一个三维数组，如果一个元素是 0，则将其所在的所有平面置为 0。解决思路与二维矩阵类似，但需要更多额外的空间来记录哪些平面需要置零。在处理高并发场景时，可以考虑使用 Redis 的 Bitmap 数据结构来存储标记位， 提升效率。
希望这篇文章能够帮助你更好地理解和掌握矩阵置零算法。 同时也希望你能举一反三，将其应用到更多实际问题中。
