Java C++ 二进制矩阵特殊位置
AnjaVon 人气:0题目要求
思路:模拟
- 直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可。
Java
class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { row[i] += mat[i][j]; col[j] += mat[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == 1 && row[i] == 1 && col[j] == 1) res++; } } return res; } }
- 时间复杂度:O(m×n)
- 空间复杂度:O(m+n)
C++
class Solution { public: int numSpecial(vector<vector<int>>& mat) { int n = mat.size(), m = mat[0].size(); int res = 0; vector<int> row(n), col(m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { row[i] += mat[i][j]; col[j] += mat[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == 1 && row[i] == 1 && col[j] == 1) res++; } } return res; } };
- 时间复杂度:O(m×n)
- 空间复杂度:O(m+n)
Rust
- 这里的迭代函数用得不是很熟练,参考了好多才勉强理解下来。
impl Solution { pub fn num_special(mat: Vec<Vec<i32>>) -> i32 { let row = mat.iter().map(|row| row.iter().sum::<i32>()).collect::<Vec<_>>(); let col = (0..mat[0].len()).map(|i| mat.iter().map(|col| col[i]).sum::<i32>()).collect::<Vec<_>>(); (0..mat.len()).fold(0, |res, i| res + (0..mat[i].len()).filter(|&j| mat[i][j] == 1 && row[i] == 1 &&col[j] == 1).count() as i32) } }
- 时间复杂度:O(m×n)
- 空间复杂度:O(m+n)
加载全部内容