73. 矩阵置零

题目描述

输入一个 m x n 的整数矩阵 matrix。

只要某个位置的值是 0，就把它所在的整行和整列全部改成 0。判断依据是修改前的原始矩阵，后来被改成 0 的位置不会再引发新的清零。

直接在 matrix 上修改，不需要返回值。

示例 1

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

解释：中心是 0，于是第 1 行和第 1 列（从 0 计）全部清零。

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

解释：第 0 行的两个 0 让第 0 行、第 0 列和第 3 列都变为 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)。能否只用常数额外空间完成？

解题思路：用第一行和第一列作标记

用首行和首列作为标记区，先记录首行首列是否含零，再扫描内部把标记写入行首列首；最后按标记清零。

为什么正确

标记阶段结束后，matrix[i][0] 与 matrix[0][j] 表示原矩阵对应行列是否需要清零。

复杂度分析

时间 O(mn)，额外空间 O(1)。

易错点

若直接边扫描边清零，会把新产生的零误认为原始零，扩大清零范围。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def setZeroes(self, matrix):
        m,n=len(matrix),len(matrix[0]); row0=any(matrix[0][j]==0 for j in range(n)); col0=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]=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 row0:
            for j in range(n): matrix[0][j]=0
        if col0:
            for i in range(m): matrix[i][0]=0

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) matrix[i][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 (row0) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (col0) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
}

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool row0 = false, col0 = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) matrix[i][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 (row0) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (col0) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
};

func setZeroes(matrix [][]int) {
	m, n := len(matrix), len(matrix[0])
	row0, col0 := false, false
	for j := 0; j < n; j++ {
		if matrix[0][j] == 0 {
			row0 = true
		}
	}
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			col0 = true
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][j] == 0 {
				matrix[i][0], matrix[0][j] = 0, 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 row0 {
		for j := 0; j < n; j++ {
			matrix[0][j] = 0
		}
	}
	if col0 {
		for i := 0; i < m; i++ {
			matrix[i][0] = 0
		}
	}
}

var setZeroes = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const row0 = matrix[0].some(v => v === 0), col0 = matrix.some(row => row[0] === 0);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) matrix[i][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 (row0) {
        for (let j = 0; j < n; j++) matrix[0][j] = 0;
    }
    if (col0) {
        for (let i = 0; i < m; i++) matrix[i][0] = 0;
    }
};

function setZeroes(matrix: number[][]): void {
    const m = matrix.length, n = matrix[0].length;
    const row0 = matrix[0].some(v => v === 0), col0 = matrix.some(row => row[0] === 0);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) matrix[i][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 (row0) {
        for (let j = 0; j < n; j++) matrix[0][j] = 0;
    }
    if (col0) {
        for (let i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

载入编辑器，自己跑一遍 →

其他解法

标记数组用 O(m+n) 额外空间换来最简单的逻辑；主解法把标记存进矩阵自己的第一行和第一列，做到 O(1) 空间，但要额外记录第一行和第一列原本是否有 0。

解法 2：使用标记数组时间 O(mn)，空间 O(m+n)

开两个布尔数组 row 和 col。第一遍扫描矩阵，遇到 0 就把所在行和列标记为 true。第二遍扫描时，只要某格所在行或列被标记，就把它置为 0。

思路最直接，不需要处理第一行和第一列被复用带来的特殊情况。代价是额外的 O(m+n) 空间，不满足进阶要求的常数空间。

class Solution:
    def setZeroes(self, matrix):
        m, n = len(matrix), len(matrix[0])
        row = [False] * m
        col = [False] * n
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True
        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m], col = new boolean[n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == 0) row[i] = col[j] = true;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (row[i] || col[j]) matrix[i][j] = 0;
    }
}

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> row(m, false), col(n, false);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == 0) row[i] = col[j] = true;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (row[i] || col[j]) matrix[i][j] = 0;
    }
};

func setZeroes(matrix [][]int) {
	m, n := len(matrix), len(matrix[0])
	row, col := make([]bool, m), make([]bool, n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 0 {
				row[i], col[j] = true, true
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if row[i] || col[j] {
				matrix[i][j] = 0
			}
		}
	}
}

var setZeroes = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const row = Array(m).fill(false), col = Array(n).fill(false);
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (matrix[i][j] === 0) row[i] = col[j] = true;
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (row[i] || col[j]) matrix[i][j] = 0;
};

function setZeroes(matrix: number[][]): void {
    const m = matrix.length, n = matrix[0].length;
    const row: boolean[] = Array(m).fill(false), col: boolean[] = Array(n).fill(false);
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (matrix[i][j] === 0) row[i] = col[j] = true;
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (row[i] || col[j]) matrix[i][j] = 0;
}

数组与矩阵专题的其他题目

查看数组与矩阵全部题目 →