Java C++ leetcode面試零矩陣

Posted on by

題目要求

思路：模擬

  • 定義兩個數組分別記錄每行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結果就隻是通過修改給出數組來標記，空間復雜度能降到常數瞭，有意義但不大

以上就是Java C++ leetcode面試零矩陣的詳細內容，更多關於Java C++ 面試零矩陣的資料請關註WalkonNet其它相關文章！

推薦閱讀：

    None Found