代码训练LeetCode(46)旋转图像

代码训练(46)矩阵置零

Author: Once Day Date: 2025年7月11日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 73. 矩阵置零 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

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

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

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

2. 分析

这个编程问题要求我们对一个给定的二维矩阵进行处理：如果矩阵中的某个元素为0，则需要将该元素所在的整行和整列的所有元素都设置为0。关键在于需要在原矩阵上直接修改，而不是使用额外的存储空间。

原题解析：

• 输入：一个 m x n 的二维矩阵。
• 处理：遍历矩阵，对于每个值为0的元素，标记其所在行和列，最后将这些行和列的所有元素设置为0。
• 输出：没有返回值，但矩阵被修改为上述规则后的状态。
• 限制：必须在原地进行操作，即不能使用额外的矩阵来进行处理。

解题思路：

1. 第一遍扫描：使用两个数组来记录哪些行和哪些列需要被置为0。这两个数组的大小分别是m和n。
2. 标记0的位置：遍历矩阵的每一个元素，如果发现元素的值为0，则将对应行和列的标记数组设置为1。
3. 第二遍扫描：再次遍历矩阵，根据标记数组的值决定是否将当前元素设置为0。

性能优化关键点：

• 空间复杂度：使用两个一维数组来存储行和列的标记，空间复杂度为O(m+n)。
• 时间复杂度：由于矩阵需要被遍历两次，时间复杂度为O(m*n)。

3. 代码实现

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = *matrixColSize;
    int row[m], col[n];
    
    // 初始化行列标记数组
    for (int i = 0; i < m; i++) {
        row[i] = 0;
    }
    for (int j = 0; j < n; j++) {
        col[j] = 0;
    }
    
    // 标记哪些行列需要被置为0
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                row[i] = 1;
                col[j] = 1;
            }
        }
    }
    
    // 置0操作
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] == 1 || col[j] == 1) {
                matrix[i][j] = 0;
            }
        }
    }
}

4. 总结

这个题目测试了数组操作和空间优化的能力。通过实践，我们学会如何在限制条件下优化解决方案，尤其是如何在原地修改数组而不使用额外空间。要提升这类问题的解决能力，可以通过练习更多关于数组和矩阵操作的题目，以及学习不同的数据结构和算法来实现更高效的解决方案。