数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 二进制矩阵中 1 和 0 集合计数程序
二进制矩阵顾名思义，只包含两个数字的矩阵，这两个数字是 1 和 0。在本文中，我们将逐步了解代码及其方法和适当的解释，以便更好地理解这些概念。在本教程中，我们将编写一个 JavaScript 程序，用于计算给定二进制矩阵中 1 和 0 的集合。
问题简介
在这个问题中，我们给定一个二进制矩阵，我们必须找到包含行或列中相同值的集合。一个集合可以是单个值，也可以是任意大小，但条件是它必须包含来自行或列的相同元素。例如，
我们给定一个具有两行三列的二进制矩阵，如下所示：
1 0 1 0 0 1
1 和 0 的集合数可以计算如下
大小为 1 的集合 - 矩阵的所有单元格本身都是不同的集合，共有 6 个单元格。
大小为 2 的集合 - 第二行的前两列具有相同的值，第二列和第三列具有相同的值，总共有 2 个大小为 2 且值相同的集合。第一行有两个 1，也可以被视为一个集合
大小为 3 的集合 - 矩阵中可能的最大集合大小是行和列的最大大小，这里为 3。但是，对于大小，没有可用的集合包含相同的值。
因此，对于大小分别为 1、2 和 3 的集合，我们总共有 6、3 和 0 个集合。因此，最终我们的答案将是 9。
方法
在上一节中，我们已经看到，我们只需要关注特定的行或列，即可获得其中相似元素的数量。此外，我们将使用数学概念来计算特定行或列中不同大小的集合的数量。
例如，如果一行中 1 的总数为 x，则大小从 1 到 x 的不同 1 集合的总数将来自排列和组合。
让我们来看一下方法：
首先，我们将获得一个数组，该数组将包含零和一，即给定的二进制矩阵。
我们将创建一个函数，自动计算传递给它作为参数的任何矩阵所需的答案，并将答案作为返回值返回。
在函数中，我们将遍历数组或二进制矩阵两次，一次用于行，第二次用于列。
在 for 循环中，我们将维护两个变量，一个用于存储 1，另一个用于存储 0 的计数。
遍历单个行或列后，我们将使用上面看到的公式更新答案，并将答案存储在我们拥有的变量中。
最后，我们将通过从中减去 rows*columns 来返回答案，因为我们已经将它们添加了两次。
我们删除了 rows * columns，因为当我们添加具有零和一的单个值的集合时，一次是在遍历行时，另一次是在遍历列时。
示例
让我们看看上面给定步骤的实现，以便更好地理解这些概念：
// given variables
var cols = 3; // no of columns
var rows = 2; // no of rows
// function to solve the problem with passed array
function fun(arr) {
// variable to store the final answer
var ans = 0;
// traversing over the rows using for loop
for (var i = 0; i < rows; i++) {
var ones = 0, zeroes = 0;
for ( var j = 0; j < cols; j++) {
if (arr[i][j] == 1)
ones++;
else
zeroes++;
}
// increasing the answer on the basis of current count based on ones
ans = ans + Math.pow(2, ones)-1;
// based on zeros
ans = ans + Math.pow(2, zeroes)-1;
}
//traversing over the columns using for loop
for (var i = 0; i < cols; i++) {
var ones = 0, zeroes = 0;
for ( var j = 0; j < rows; j++) {
if (arr[j][i] == 1)
ones++;
else
zeroes++;
}
//increasing the answer on the basis of current count based on ones
ans = ans + Math.pow(2, ones)-1;
// based on zeros
ans = ans + Math.pow(2, zeroes)-1;
}
return ans - (rows * cols);
}
var arr = [ [ 1, 0, 1 ], [ 0, 1, 0 ] ];
console.log("Total number of the sets in the given binary matrix is: " + fun(arr));
时间和空间复杂度
上面代码的时间复杂度为 O(N*N)，其中 N 是给定矩阵中行数和列数的最大值。
没有使用额外的空间，因此代码的空间复杂度为 O(1)。
结论
在本教程中，我们学习了如何编写一个 JavaScript 程序，用于计算给定二进制矩阵中 1 和 0 的集合。二进制矩阵顾名思义，只包含两个数字的矩阵，这两个数字是 1 和 0。所讨论代码的时间复杂度为 O(N*N)，空间复杂度为 O(1)。
271 次查看
