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

王林转载: 2023-08-25 17:01:22 689浏览

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

输入

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]

说明

我们可以使用交换算法并获得结果，我们将在下一节中实现它。

递归方法

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

如果第一个数组的大小很小，那么我们将交换第一个数组的元素，最后一个元素等于第一个数组的大小，如果第一个数组的大小大于我们将交换第一个数组elements 等于给定数组的第二个数组的大小。

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

示例

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);