73. 矩阵置零

力扣题目链接 (opens new window)

题目描述

给定一个 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 <= matrix[i][j] <= 2^31 - 1

进阶：

• 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

思路

暴力思路

最直观的想法是，先遍历一遍矩阵，用两个数组分别记录哪些行、哪些列需要置零，然后再遍历一遍矩阵进行置零操作。

这样需要O(m + n)的额外空间。

原地标记法

能不能不用额外空间呢？

关键点是：我们可以用矩阵的第一行和第一列来充当标记数组的角色。

具体来说：

• 如果matrix[i][j] == 0，我们就把matrix[i][0]和matrix[0][j]标记为0
• 这样第一行和第一列就记录了哪些行、哪些列需要置零

但有个问题：第一行和第一列本身可能就有0，我们怎么区分是原本就有0，还是被标记的0呢？

所以需要两个变量，单独记录第一行和第一列本身是否需要置零。

整体流程：

1. 用firstRowHasZero和firstColHasZero记录第一行和第一列本身是否有0
2. 遍历矩阵（除了第一行第一列），如果matrix[i][j] == 0，就把matrix[i][0]和matrix[0][j]标记为0
3. 根据第一行和第一列的标记，对矩阵（除了第一行第一列）进行置零
4. 最后根据firstRowHasZero和firstColHasZero，对第一行和第一列进行置零

为什么要把第一行第一列放到最后处理？

因为如果先处理第一行第一列，就会破坏标记信息，导致后续的置零操作出错。

模拟过程

以 matrix = [[1,1,1],[1,0,1],[1,1,1]] 为例：

第1步：标记阶段

发现 matrix[1][1] = 0，将 matrix[1][0] 和 matrix[0][1] 标记为 0。第一行和第一列本身是否有 0，用两个变量单独记录。

第2步：置零

根据第一行和第一列的标记，将对应的行和列置零。先处理内部元素，最后处理第一行和第一列（避免标记信息被提前覆盖）。

解题代码

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        // 记录第一行和第一列本身是否有0
        bool firstRowHasZero = false;
        bool firstColHasZero = false;
        
        // 检查第一行是否有0
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }
        
        // 检查第一列是否有0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
        
        // 遍历矩阵（除了第一行第一列），用第一行和第一列记录标记
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;  // 标记该行
                    matrix[0][j] = 0;  // 标记该列
                }
            }
        }
        
        // 根据标记，对矩阵（除了第一行第一列）进行置零
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 最后处理第一行
        if (firstRowHasZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // 最后处理第一列
        if (firstColHasZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

复杂度分析

• 时间复杂度：O(m × n)，需要遍历矩阵两次
• 空间复杂度：O(1)，只使用了常量级别的额外空间

其他语言

Python3

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        
        # 记录第一行和第一列本身是否有0
        first_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))
        
        # 遍历矩阵（除了第一行第一列），用第一行和第一列记录标记
        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

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 记录第一行和第一列本身是否有0
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;
        
        // 检查第一行是否有0
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }
        
        // 检查第一列是否有0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
        
        // 遍历矩阵（除了第一行第一列），用第一行和第一列记录标记
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;  // 标记该行
                    matrix[0][j] = 0;  // 标记该列
                }
            }
        }
        
        // 根据标记，对矩阵（除了第一行第一列）进行置零
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 最后处理第一行
        if (firstRowHasZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // 最后处理第一列
        if (firstColHasZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

Go

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    
    // 记录第一行和第一列本身是否有0
    firstRowHasZero := false
    firstColHasZero := false
    
    // 检查第一行是否有0
    for j := 0; j < n; j++ {
        if matrix[0][j] == 0 {
            firstRowHasZero = true
            break
        }
    }
    
    // 检查第一列是否有0
    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            firstColHasZero = true
            break
        }
    }
    
    // 遍历矩阵（除了第一行第一列），用第一行和第一列记录标记
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0  // 标记该行
                matrix[0][j] = 0  // 标记该列
            }
        }
    }
    
    // 根据标记，对矩阵（除了第一行第一列）进行置零
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    
    // 最后处理第一行
    if firstRowHasZero {
        for j := 0; j < n; j++ {
            matrix[0][j] = 0
        }
    }
    
    // 最后处理第一列
    if firstColHasZero {
        for i := 0; i < m; i++ {
            matrix[i][0] = 0
        }
    }
}

JavaScript

var setZeroes = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    // 记录第一行和第一列本身是否有0
    let firstRowHasZero = false;
    let firstColHasZero = false;
    
    // 检查第一行是否有0
    for (let j = 0; j < n; j++) {
        if (matrix[0][j] === 0) {
            firstRowHasZero = true;
            break;
        }
    }
    
    // 检查第一列是否有0
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            firstColHasZero = true;
            break;
        }
    }
    
    // 遍历矩阵（除了第一行第一列），用第一行和第一列记录标记
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;  // 标记该行
                matrix[0][j] = 0;  // 标记该列
            }
        }
    }
    
    // 根据标记，对矩阵（除了第一行第一列）进行置零
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    // 最后处理第一行
    if (firstRowHasZero) {
        for (let j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
    
    // 最后处理第一列
    if (firstColHasZero) {
        for (let i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
};

与代码随想录联系

这道题的核心在于原地标记的技巧，巧妙利用矩阵本身的第一行和第一列来存储标记信息。

这种"就地复用"的思想在很多算法题中都有体现，比如数组题中用负数标记访问过的位置，链表题中用快慢指针等。

本题考察的是对矩阵遍历顺序的把握，以及如何避免标记信息被过早覆盖。录友们做完这道题后，建议画图模拟一遍整个过程，理解为什么要把第一行第一列放到最后处理。