2023JavaScript 程序检查矩阵是否为上三角

上三角矩阵是一个方阵，具有相同的行数和列数，并且主对角线下方的所有元素从第一个单元格（位于左上角）到最后一个单元格（位于左上角）右下角）为零。上三角形意味着下三角形中存在的元素将为零。我们将实现一个适当的代码，并对时间和空间复杂性进行解释和讨论。

示例

Input1:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
Output1: Yes,

解释：我们可以看到主对角线包含元素 1、5、8 和 1，并且主对角线下方的所有单元格的值都为零。

Input2:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
]
Output1: No

解释：我们可以看到主对角线包含元素 1、5、8 和 1，并且主对角线下方的所有单元格的值都不为零，因为最后一行的第二列包含非零值值。

方法

我们已经看到了上面的示例，现在让我们看看实现代码的步骤：

首先，我们将创建一个函数，在其中传递给定的矩阵。我们将仅遍历矩阵的主对角线下侧部分，即每个单元格 (i,j)，其中 j 小于 i。如果我们发现任何单元格具有非零值，我们将返回 false，否则最终我们将返回 true。

示例

// function to traverse over the matrix
function check(mat){

   // getting total number of rows of matrix
   var rows = mat.length
   
   // traversing over the section present above the main diagonal
   for(var i = 0; i < rows; i++){
      for(var j = 0; j < i; j++){
         if(mat[i][j] != 0){
            return false;
         }
      }
   }
   return true;
}

// defining the matrix
var mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

// updating matrix
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
      ]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

输出

The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 0, 0, 1 ] ]
The given matrix is an upper triangular matrix
The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 1, 0, 1 ] ]
The given matrix is not an upper triangular matrix

时间和空间复杂度

上述代码的时间复杂度为O(N*N)，其中N是给定矩阵的行数。这是因为我们只遍历了矩阵一次。

上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个 JavaScript 程序来检查给定矩阵是否是上三角矩阵。上三角形意味着下三角形中存在的元素将为零。我们遍历了矩阵中列数小于行数的单元格，时间复杂度为 O(N*N)，空间复杂度为 O(1)。