Java C++ leetcode面试零矩阵
题目要求
思路：模拟
- 定义两个数组分别记录每行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++ 面试零矩阵的资料请关注其它相关文章！
相关文章