矩阵零置换问题

题解思路

本题要求我们在一个 m × n 的矩阵中，如果某个元素为 0，则将其所在行和列的所有元素都设为 0。同时，需要使用原地算法，即不额外使用额外的存储空间（或尽可能减少额外空间的使用）。

我们可以采取如下方法：

1. 第一遍遍历：标记零元素的位置

   • 使用两个数组 row_flag 和 col_flag 分别记录需要清零的行和列，大小分别为 m 和 n。
   • 遍历整个矩阵，找到 0 位置时，将对应的 row_flag[i] 和 col_flag[j] 设为 True。

2. 第二遍遍历：将行和列清零

   • 再次遍历矩阵，如果当前行 i 或列 j 被标记，则将 matrix[i][j] 置为 0。

3. 优化方案（使用矩阵本身的第一行和第一列作为标记）

   • 由于 row_flag 和 col_flag 额外占用 O(m + n) 空间，我们可以用矩阵的第一行和第一列来存储这些标记。
   • 额外使用两个变量 row_zero 和 col_zero 记录第一行和第一列是否需要清零，避免污染原始数据。
   • 遍历矩阵时，使用 matrix[0][j] 标记第 j 列是否需要清零，使用 matrix[i][0] 标记第 i 行是否需要清零。

时间复杂度

• 我们需要遍历矩阵两遍，一次用于标记，一次用于清零，总共 O(2 * m * n)，即 O(m * n) 。

空间复杂度

• 使用额外数组 O(m + n) 的方法：额外的行和列数组需要 O(m + n) 空间。
• 优化后使用原矩阵第一行和第一列：额外空间只需要 O(1)。

代码

Python 代码

class Solution:
    def setZeroes(self, matrix):
        if not matrix:
            return
        
        m, n = len(matrix), len(matrix[0])
        row_zero = any(matrix[0][j] == 0 for j in range(n))
        col_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 row_zero:
            for j in range(n):
                matrix[0][j] = 0

        # 处理第一列
        if col_zero:
            for i in range(m):
                matrix[i][0] = 0

# 读取输入并处理
if __name__ == "__main__":
    m, n = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(m)]

    solution = Solution()
    solution.setZeroes(matrix)

    for row in matrix:
        print(" ".join(map(str, row)))

Java 代码

import java.util.*;

public class Main {
    public class Solution {
        public void setZeroes(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            boolean rowZero = false, colZero = false;

            // 记录第一行和第一列是否含有零
            for (int i = 0; i < m; i++) {
                if (matrix[i][0] == 0) colZero = true;
            }
            for (int j = 0; j < n; j++) {
                if (matrix[0][j] == 0) rowZero = true;
            }

            // 使用第一行和第一列记录需要清零的行和列
            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 (rowZero) {
                for (int j = 0; j < n; j++) {
                    matrix[0][j] = 0;
                }
            }

            // 处理第一列
            if (colZero) {
                for (int i = 0; i < m; i++) {
                    matrix[i][0] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] matrix = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        Main main = new Main();
        Solution solution = main.new Solution();
        solution.setZeroes(matrix);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        scanner.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool rowZero = false, colZero = false;

        // 记录第一行和第一列是否含有零
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) colZero = true;
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) rowZero = true;
        }

        // 使用第一行和第一列记录需要清零的行和列
        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 (rowZero) fill(matrix[0].begin(), matrix[0].end(), 0);

        // 处理第一列
        if (colZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> matrix(m, vector<int>(n));

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];

    Solution().setZeroes(matrix);

    for (const auto& row : matrix) {
        for (int num : row) cout << num << " ";
        cout << endl;
    }
    return 0;
}

Leetcode 18.矩阵置零-原题链接

题目内容

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

输入描述

第一行两个整数$m，n$ 接下来$m$行，每行$n$列，代表输入的矩阵。 每行的数字之间以空格分隔。

输出描述

输出操作后的矩阵。

样例1

输入

3 3
1 1 1
1 0 1
1 1 1

输出

1 0 1
0 0 0
1 0 1

样例2

输入

3 4
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$