JavaScript 在一个正方形矩阵中查找最大和最小的程序
要找到最大或最小的元素,我们必须关注我们将进行多少次比较以及选择哪种方法进行比较的效率:一种是使用if-else语句比较元素的方法,另一种是使用内置的方法。我们将看到完整的代码实现和解释。在本文中,我们将实现一个用于查找给定正方形矩阵中最大和最小元素的JavaScript程序。
问题介绍
这个问题非常简单,但是深入研究将带来一些很好的突出概念值得学习。
在这个问题中,我们给出了一个矩阵,对于该矩阵,我们必须找到其中存在的最大和最小元素。例如,如果矩阵是-
Mat = [ 1, 3, 7,
5, 2, 9,
2, 5, 1]
从上述矩阵可以看出,1是最小的元素,9是最大的元素。
让我们看看针对这个问题的方法及其代码实现:
原生方法
在这种方法中,我们将一次遍历所有元素,并检查它们是否大于当前元素。步骤如下:
- 首先,我们将创建一个函数来传递不同的矩阵并得到结果。
-
对于给定的矩阵,我们将获取其行和列,以便使用for循环遍历它。
-
我们将创建两个变量来存储最小和最大元素,并将它们初始化为1000000000,假设矩阵的元素小于等于这个值。
-
同样,我们将通过将元素的值初始化为-1000000000来将最大元素初始化为这个值,假设矩阵的元素大于等于这个值。
-
使用for循环遍历矩阵,并对于每个索引,我们将使用两个if-else条件。
-
通过进行必要的比较,我们将更新最大值和最小值。
示例
// creating a function to get the minimum and maximum number
function min_max(matrix){
// getting rows and columns of given matrix
var rows = matrix.length
var cols = matrix[0].length
var min_ans = 1000000000
var max_ans = -1000000000
// traversing over the matrix
for(var i = 0; i<rows; i++){
for(var j = 0; j<cols; j++){
if(min_ans > matrix[i][j]){
min_ans = matrix[i][j];
}
if(max_ans < matrix[i][j]) {
max_ans = matrix[i][j];
}
}
}
console.log("The maximum element present in the Matrix is: " + max_ans);
console.log("The minimum element present in the Matrix is: " + min_ans);
}
// defining the matrix
Mat = [ [1, 3, 7],
[5, 2, 9],
[2, 5, 1] ]
// calling the function
min_max(Mat)
时间和空间复杂度
以上代码的时间复杂度为O(N*M),其中N和M分别为行数和列数。同时,空间复杂度为O(1)。
这里的主要问题不是时间复杂度,而是我们进行的比较次数。在以上代码中,我们进行了N * M * 2次比较,因为对于每个索引,我们都检查了最小和最大元素。
比较高效的方法
这种方法在大部分部分与上述方法相似,但在比较部分,我们现在将进行3/2 * N * M次比较,通过更新一些if-else语句。让我们来看看代码-
示例
// creating a function to get the minimum and maximum number
function min_max(matrix){
// getting rows and columns of given matrix
var rows = matrix.length
var cols = matrix[0].length
var min_ans = 1000000000
var max_ans = -1000000000
// traversing over the matrix
for(var i = 0; i<rows; i++){
for(var j = 0; j<=cols/2; j++){
if (matrix[i][j] > matrix[i][rows - j - 1]){
if (min_ans > matrix[i][cols - j - 1])
min_ans = matrix[i][cols - j - 1];
if (max_ans< matrix[i][j])
max_ans = matrix[i][j];
} else {
if (min_ans > matrix[i][j])
min_ans = matrix[i][j];
if (max_ans < matrix[i][cols - j - 1])
max_ans = matrix[i][cols - j - 1];
}
}
}
console.log("The maximum element present in the Matrix is: " + max_ans);
console.log("The minimum element present in the Matrix is: " + min_ans);
}
// defining the matrix
Mat = [ [1, 3, 7],
[5, 2, 9],
[2, 5, 1] ]
// calling the function
min_max(Mat)
时间和空间复杂度
上述代码的时间复杂度为O(N*M),其中N和M分别是行和列的个数。此外,空间复杂度为O(1)。
相比之前,比较的次数少了,现在是3/2 * (N*M)。
结论
在本教程中,我们将实现一个JavaScript程序,用于找到给定方阵中的最大和最小元素。我们遍历了给定的矩阵,并将每个元素与存储答案的变量进行比较。讨论了两种技术:一种是比较次数为2NM,另一种是比较次数为3/2 NM,但这两种方法的空间复杂度相同。