JavaScript程序：计算二进制矩阵中1和0的集合数

二进制矩阵是一个只由两个数字组成的矩阵，如其名所示，这两个数字是1和0。在本文中，我们将通过代码和适当的解释来更好地理解概念。在本教程中，我们将编写一个JavaScript程序来计算给定二进制矩阵中1和0的集合。

问题介绍

在这个问题中，我们给定了一个二进制矩阵，我们需要找到包含相同值的行或列的集合。一个集合可以是单个值，也可以是任意大小，但条件是它必须包含来自行或列的相同元素。例如，

我们有一个二进制矩阵，它有两行三列，看起来像这样 –

1 0 1
0 0 1

1和0的集合数量可以计算为

• Set of size 1 − All the cells of the matrix are distinct sets in itself and there is a total of 6 cells.

• 大小为2的集合 – 第二行的前两列具有相同的值，第二列和第三列的值也相同，共有2个大小为2且具有相同值的集合。第一行还有两个1可以被视为一个集合

• 大小为3的集合 – 矩阵中可能的最大集合大小是行和列的最大大小，这里是3。但是，对于大小，没有可用的包含相同值的集合。

因此，我们分别有6个、3个和0个套装可用于尺寸为1、2和3的情况。因此，最终我们的答案将是9。

方法

In the previous section, we have seen that we have to focus on only a particular row or column to get the number of similar elements in it. Also, we will use a mathematical concept to count the number of sets with different sizes present in a particular row or column.

例如，如果我们在行中有x个1的总数，则不同大小为1到x的1的集合的总数将来自于排列组合。

让我们转向这种方法 –

• 首先，我们将获得一个包含零和一的数组，或者说是给定的二进制矩阵。

• 我们将创建一个函数，用于自动计算传递给它作为参数的任何矩阵的所需答案，并将答案作为返回值返回。

• 在这个函数中，我们将两次遍历数组或二进制矩阵，一次是按行，第二次是按列。

• 在for循环中，我们将维护两个变量，一个用于存储1的个数，另一个用于存储0的个数。

• 在遍历完单行或单列后，我们将使用上面所见的公式更新答案，并将答案存储在我们的变量中。

• 最后，我们将通过从中删除行*列来返回答案，因为我们已经将它们添加了两次。

我们已经移除了行 * 列，因为在遍历行时，将集合与两个零和一个一的单值相加，而在遍历列时又进行了一次。

Example

的中文翻译为：

示例

让我们来看看上述步骤的实现，以更好地理解这些概念 –

// 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)。