Java C面试，如何巧妙改写LeetCode零矩阵问题为长尾？

本文共计601个文字，预计阅读时间需要3分钟。

目录 + 项目要求 + 思路：模拟 + Java + C++ + Rust + 总结 + 项目要求 + 思路：模拟 + 定义两个数组分别记录每行或每列中为0的元素；0所在行（列）清零 + 【伪代码】

目录

• 题目要求
• 思路：模拟
• 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++ 面试零矩阵的资料请关注自由互联其它相关文章！