Java C++ 面试零矩阵

时间:2022-10-20 AnjaVon 人气:0

题目要求

思路：模拟

定义两个数组分别记录每行or每列中为0的元素；
0所在的行列清零也就意味着元素所在行or列有0则置零【废话连篇】；
所以一次遍历找出有0的行列，一次遍历根据其将相应元素置零。

Java

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

时间复杂度：O(n×m)
空间复杂度：O(n+m)

C++

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

时间复杂度：O(n×m)
空间复杂度：O(n+m)

Rust

impl Solution {
    pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
        let (n, m) = (matrix.len(), matrix[0].len());
        let (mut rows, mut cols) = (vec![false; n], vec![false; m]);
        for i in 0..n {
            for j in 0..m {
                if matrix[i][j] == 0 {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for i in 0.. n {
            for j in 0..m {
                if rows[i] || cols[j] {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

时间复杂度：O(n×m)
空间复杂度：O(n+m)

总结

因为是中等题所以纠结了半天是不是有什么精巧奇妙的算法解题……emmmm结果就只是通过修改给出数组来标记，空间复杂度能降到常数了，有意义但不大

加载全部内容