Java C++ leetcode面试零矩阵
目录
- 题目要求
- 思路:模拟
- Java
- C++
- Rust
- 总结
题目要求
思路:模拟
- 定义两个数组分别记录每行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++ 面试零矩阵的资料请关注我们其它相关文章!
赞 (0)