JavaScript 用于数组旋转的块交换算法

数组元素的旋转意味着将给定数组的元素移动到左侧或右侧特定位置的某个位置。我们假设数组呈循环形式，并将边界的元素旋转到另一端。数组旋转的块交换算法意味着通过给定的数字旋转数组的元素，但不使用旋转技术，而是使用交换技术。我们将实现递归和迭代两种方法。

输入

The given array is [ 1, 2, 3, 4, 5, 6, 7].
The number of rotations by which we have to rotate is 3.

输出

[4, 5, 6, 7, 1, 2, 3]

解释

我们可以使用交换算法，并得到结果，我们将在下一部分中实现。

递归方法

在这种方法中，我们假设我们有两个数组，第一个数组的大小与给定的旋转次数相同，另一个数组的大小为总数减去给定的元素个数。

如果第一个数组的大小较小，我们将交换第一个数组的元素与最后大小为第一个数组大小的元素，如果第一个数组的大小更大，我们将交换第一个数组大小个元素与给定数组。

对于剩余的元素，我们将通过更换交换的数组来调用递归函数。

示例

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }

   // special case when the number of elements to rotate 
   // is half of the size of the given array
   if(n == 2*k){
      arr = swap(arr, 0, n - k, k);
      return;
   }        

   // if the first part is short    
   if(2*k < n) {
      arr = swap(arr, 0, n - k, k);
      rotate(arr, k, n - k);    
   }
   else{    

      // if second part is short
      arr = swap(arr, 0, k, n - k);
      rotate(arr + n - k, 2 * k - n, k);
   }
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

//Defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);

时间和空间复杂度

以上代码的时间复杂度是N，其中N是给定数组的大小。

以上代码的空间复杂度是N，但只有在考虑递归栈占用的内存时才是如此。

迭代方法

迭代方法与递归方法相同，唯一的区别是我们在while循环中工作，而不使用递归调用。让我们看看代码。

示例

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }
   var i = k;
   var j = n - k;
   while (i != j){
      if(i < j){

         // if the first array is shorter 
         arr = swap(arr, k - i, k + j - i, i);
         j -= i;
      }
      else{ 

         // if the second array is shorter 
         arr = swap(arr, k - i, k, j);
         i -= j;
      }
   }
   arr = swap(arr, k - i, k, i);
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

// defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);