資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 程式檢查給定矩陣是否為稀疏矩陣
在數學中，矩陣是一組以矩形形式儲存的整數或數字，相當於程式設計或 JavaScript 程式設計中的二維陣列。稀疏矩陣是一種特殊的矩陣，其中零的數量嚴格大於給定矩陣中存在的元素或數字的總數。我們將得到一個矩陣，我們必須找出當前矩陣是否為稀疏矩陣。
輸入
Mat = [ [1, 0, 0], [0, 3, 4], [8, 0, 0]]
輸出
Yes, the given matrix is a sparse matrix.
解釋
在上面的矩陣中，我們總共有 5 個零，給定矩陣中的整數總數為 9，這意味著當前矩陣是稀疏矩陣。
輸入
Mat = [ [1, 2, 3, 4], [0, 0, 0, 0], [5, 6, 7, 8], [0, 0, 0, 0]]
輸出
No, the given matrix is not a sparse matrix.
解釋
給定矩陣中共有 16 個元素，並且存在 8 個零。根據定義，我們需要大多數元素為零，這意味著嚴格超過一半的元素必須為零。
方法
我們已經看過示例來理解問題，現在讓我們轉到我們將遵循的實現程式碼的步驟 -
首先，我們將建立一個函式，該函式將給定矩陣作為引數並返回矩陣中存在的零的數量。
我們將使用巢狀的 for 迴圈遍歷矩陣，並使用一個變數來儲存零的數量。
我們將呼叫該函式並將返回值儲存在一個變數中並進行檢查。
如果零的數量小於或等於總變數數量的一半，則列印它不是稀疏矩陣。
否則，我們將列印給定矩陣是稀疏矩陣。
示例
// function to count number of zeros present in the given matrix
function countZeros(mat){
// getting the number of rows present in the given matrix.
var n = mat.length;
// getting the number of columns present in the given matrix.
var m = mat.length;
var count = 0; // variable to count number of zeros
// traversing over the given matrix
for(var i = 0;i < n; i++){
for(var j = 0; j<m; j++){
// if current element is zero increase the count
if(mat[i][j] == 0){
count++;
}
}
}
// returing true as all the values matched
return count;
}
// defining the matrix
var mat = [ [1, 0, 0],
[0, 3, 4],
[8, 0, 0]]
console.log("The given matrix is: ")
console.log(mat);
// counting number of zeros in the given matrix
var zeros = countZeros(mat);
var size = (mat.length)*(mat[0].length);
if(zeros > size/2){
console.log("The given matrix is a sparse matrix")
}
else{
console.log("The given matrix is not a sparse matrix")
}
時間和空間複雜度
以上程式碼的時間複雜度為 O(N*M)，其中 N 是給定矩陣的行數，M 是給定矩陣的列數。
以上程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間來儲存矩陣。
結論
在本教程中，我們實現了一個 JavaScript 程式來檢查給定矩陣是否為稀疏矩陣。稀疏矩陣是一種特殊的矩陣，其中零的數量嚴格大於給定矩陣中存在的元素或數字的總數。我們已在 O(N*M) 時間複雜度下實現了程式碼，並在 O(1) 空間複雜度下工作。
更新於: 2023年4月20日
125 次檢視
廣告