JavaScript程序用于检查矩阵的所有行是否彼此为循环旋转

WBOY 转载: 2023-08-21 22:45:08 758浏览

Matrix is a kind of 2-D array in which there is an array of fixed arrays that defines the rows and for each index of this array there are fixed length arrays present and the length of these arrays defines the number of columns present in the matrix. We can store any kind of data type in these cells provided by the matrix.

We will be provided with a matrix and each row contains some integers and we have to check if each row is the rotation of one another or not. Rotation of each other means by some number or left or right rotations we can produce the same combination of each row.

Example 1

让我们假设给定的矩阵是：

mat = [ [1, 2, 3],
   [2, 3, 1],
   [3, 1, 2]]
Output: Yes

Explanation: Assuming the first row is constant and rotating the remaining one we can get the result as:

By rotating the second row one time to the right and rotating the second row two times to the right we can make both same as the first row.

Example 2

的翻译为：

示例2

mat = [ [1, 2, 3],
   [ 2, 1, 3],
   [ 1, 2, 3]]
Output: No

解释：在上面的矩阵中，第一行和第三行是相同的，但我们无法通过任意次数的旋转将第二行转换为第一行。

Approach

We have seen a proper example for understanding of the problem now let us see the steps to implement the code −

首先，我们将定义一个函数rotate，使用两个指针和交换技术来旋转作为参数传递给它的数组的元素。
之后，我们将定义检查函数，并将给定的矩阵传递给检查函数。
在该函数中，我们首先通过获取行和列的数量来获取矩阵的长度，并使用for循环从第1行到最后一行与第0行进行比较。
如果当前行与第一行相同，则我们将跳过到下一行。
否则，我们将调用 rotate 函数，并将给定的行旋转到其下一个旋转位置。
We will do this process until we find the same array as the zeroth row or length of columns numbers of times.
If the current row is not equal to the zeroth even after the maximum rotations then we will return false.
如果所有的行最终变得相等，那么我们将返回true。

Example

在下面的示例中，我们检查矩阵的所有行是否是彼此的循环旋转。输入和预期输出如下所示。

输入：matrix = [ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ]

Output: Yes

// function to rotate the given array
function rotate(arr){
   var l = 0;
   var r = arr.length-1;
   while(l < r){
      arr[l] += arr[r];
      arr[r] = arr[l]-arr[r];
      arr[l] = arr[l]-arr[r];
      l++;
   }
   return arr;
}

// function to check if the given matrix can have the same rows
// after the certain number of rotations
function check(mat){

   // getting number of rows
   var rows = mat.length
   
   // getting number of columns
   var cols = mat[0].length
   
   // traversing over the each row of given matrix
   for(var i = 1; i < rows; i++){
      var k = 0;
      while(k < cols) {
         var j = 0;
         for(j = 0; j<cols; j++){
            if(mat[0][j] != mat[i][j]){
               break;
            }
         }
         if(j == cols){
            break;
         }
         else{
            mat[i] = rotate(mat[i]);
         }
         k++;
      }
      if(k == cols){
         return false;
      }
   }
   return true;
}

// defining the matrix
var mat = [ [1, 2, 3],
   [2, 3, 1],
   [3, 1, 2]];
console.log("The given matrix is: ");
console.log(mat);
if(check(mat) == true){
   console.log("Yes, all the rows of the matrix are circular rotation of each other");
}
else{
   console.log("NO, all the rows of the matrix are not in the circular rotation of each other");
}

输出

The given matrix is: 
[ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ]
Yes, all the rows of the matrix are circular rotation of each other

时间和空间复杂度

The time complexity of the above code is O(N*M*M) where N is the number or rows and M is the number of columns present in the given matrix. We are traversing over the matrix row wise gives the factor or N and for comparison and rotations of the row’s givens the factor or M*M.

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