資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
