JavaScript 检查矩阵的每一行是否是彼此的循环旋转

矩阵是一种二维数组，其中包含固定数组的组合来定义行，对于这个数组的每个索引来说，有固定长度的数组，并且这些数组的长度定义了矩阵中的列数。我们可以在矩阵提供的单元格中存储任何类型的数据。

我们将会获得一个矩阵，每行包含一些整数，我们需要检查每行是否是彼此的旋转。彼此的旋转意味着通过一些数字的或向左或向右的旋转，我们可以产生每行的相同组合。

示例1

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

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

解释：假设第一行是固定的，将剩下的一行旋转，我们可以得到结果如下：

通过将第二行向右旋转一次和将第二行向右旋转两次，我们可以使两行与第一行相同。

示例2

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

解释：在上面的矩阵中，第一行和第三行是相同的，但是我们无论进行多少次旋转，都不能将第二行转换为第一行。

方法

我们已经看到一个适当的示例来理解问题，现在让我们看看实现代码的步骤：

• 首先，我们将定义一个函数rotate，使用两个指针和交换技术将作为参数传递给它的数组的元素旋转。

• 然后，我们将定义check函数并将给定的矩阵传递给它进行检查。

• 在函数中，首先我们将通过获取行和列并使用for循环检查从1到最后的每一行。

• 如果当前行与第一行相同，则我们将继续下一行。

• 否则，我们将调用rotate函数并将给定行旋转到其下一个旋转。

• 我们将重复此过程，直到我们找到与第零行相同的数组或列数的长度。

• 如果即使在最大旋转次数之后，当前行仍不等于第零行，则返回false。

• 如果所有行最终变得相等，则返回true。

示例

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

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

输出：是

// 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

时间和空间复杂度

上述代码的时间复杂度为O(NMM)，其中N为给定矩阵中的行数，M为列数。我们按照行遍历矩阵，这给出了因子N，而对行进行比较和旋转给出了因子M*M。

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

结论

在本教程中，我们实现了JavaScript程序，通过旋转每一行并与第一行进行比较，来检查给定矩阵的所有行是否是彼此的循环旋转。我们使用了两个指针和交换方法来旋转给定矩阵的行。上述代码的时间复杂度为O(NMM)，空间复杂度为O(1)。