JavaC如何解决LeetCode 1582二进制矩阵特殊位置问题？

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

目录- 题目要求- 思路- 模拟- Java- C++- Rust

题目要求：模拟一个算法，该算法接收一个整数数组，计算数组中每行每列1的个数，并判断是否存在一行或一列的1的个数等于数组行数或列数。如果存在，返回该行或列的索引；如果都不存在，返回-1。

思路：

1.遍历数组，记录每行和每列1的个数。

2.检查每行和每列的1的个数是否等于数组的行数或列数。

3.如果找到符合条件的行或列，返回其索引；否则，返回-1。

模拟：

直接按题目要求模拟。

Java：javaclass Solution { public int numSpecial(int[][] grid) { int rows=grid.length; int cols=grid[0].length; int[] rowCounts=new int[rows]; int[] colCounts=new int[cols];

// 计算每行和每列1的个数 for (int i=0; i

// 检查每行和每列 for (int i=0; i

return -1; }}

C++：cppclass Solution {public: int numSpecial(vector& grid) { int rows=grid.size(); int cols=grid[0].size(); vector rowCounts(rows, 0); vector colCounts(cols, 0);

// 计算每行和每列1的个数 for (int i=0; i

// 检查每行和每列 for (int i=0; i

return -1; }}

Rust：ruststruct Solution;

impl Solution { fn num_special(grid: Vec) -> i32 { let rows=grid.len(); let cols=grid[0].len(); let mut row_counts=vec![0; rows]; let mut col_counts=vec![0; cols];

// 计算每行和每列1的个数 for i in 0..rows { for j in 0..cols { if grid[i][j]==1 { row_counts[i] +=1; col_counts[j] +=1; } } }

// 检查每行和每列 for i in 0..rows { if row_counts[i]==rows as i32 { return i as i32; } } for j in 0..cols { if col_counts[j]==cols as i32 { return j as i32; } }

-1 }}

目录

• 题目要求
• 思路：模拟
• Java
• C++
• Rust

题目要求

思路：模拟

• 直接按题意模拟，先算出每行每列中“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)

以上就是Java C++ 算法题解leetcode1582二进制矩阵特殊位置的详细内容，更多关于Java C++ 二进制矩阵特殊位置的资料请关注自由互联其它相关文章！