用於數組旋轉的區塊交換演算法的 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]

說明

我們可以使用交換演算法並獲得結果，我們將在下一節中實現它。

遞迴方法

在這個方法中，我們將嘗試假設我們有兩個數組，第一個數組的大小為給定的旋轉數，另一個數組的大小為總大小減去給定的元素數。

如果第一個數組的大小很小，那麼我們將交換第一個數組的元素，最後一個元素等於第一個數組的大小，如果第一個數組的大小大於我們將交換第一個數組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);

時間與空間複雜度

上述程式碼的時間複雜度為N，其中N是給定陣列的大小。

上述程式碼的空間複雜度為 1 或常數，因為我們在這裡沒有使用任何額外的空間。

結論

在本教程中，我們實作了一個 JavaScript 程序，透過使用區塊交換演算法將陣列旋轉給定的旋轉次數。我們使用 O(N) 時間和 O(1) 空間複雜度的迭代方法實作了區塊交換演算法，同時使用遞歸方法實作了 O(N) 空間複雜度。

以上是用於數組旋轉的區塊交換演算法的 JavaScript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！