JavaScript-Programm für den Blockaustauschalgorithmus für die Array-Rotation

Durch Drehen von Array-Elementen werden die Elemente eines bestimmten Arrays um eine bestimmte Anzahl von Positionen nach links oder rechts verschoben. Wir gehen davon aus, dass das Array die Form einer Schleife hat und drehen die Elemente von der Kante zum anderen Ende. Der Block-Swap-Algorithmus für die Array-Rotation bedeutet, dass die Elemente des Arrays um einen bestimmten Betrag gedreht werden. Anstelle von Drehungen wird jedoch eine Austauschtechnik verwendet. Wir werden rekursive und iterative Methoden implementieren.

Eintreten

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

Ausgabe

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

Anleitung

Wir können den Austauschalgorithmus verwenden und das Ergebnis erhalten. Wir werden es im nächsten Abschnitt implementieren.

Rekursive Methode

Bei dieser Methode versuchen wir anzunehmen, dass wir zwei Arrays haben, das erste hat die Größe der angegebenen Anzahl von Drehungen und das andere die Größe der Gesamtgröße minus der angegebenen Anzahl von Elementen.

Wenn die Größe des ersten Arrays klein ist, tauschen wir die Elemente des ersten Arrays aus und das letzte Element entspricht der Größe des ersten Arrays. Wenn die Größe des ersten Arrays größer ist, tauschen wir die Elemente aus Das erste Array entspricht der Größe des zweiten Arrays des angegebenen Arrays.

Für die verbleibenden Elemente rufen wir die rekursive Funktion auf, indem wir das Swap-Array ändern.

Beispiel

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt N, wobei N die Größe des angegebenen Arrays ist.

Der obige Code hat eine Raumkomplexität von N, aber das gilt nur, wenn wir den vom rekursiven Stapel belegten Speicher berücksichtigen.

Iterative Methode

Die iterative Methode ist die gleiche wie die rekursive Methode, der einzige Unterschied besteht darin, dass wir in einer While-Schleife arbeiten, anstatt rekursive Aufrufe zu verwenden. Schauen wir uns den Code an.

Beispiel

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt N, wobei N die Größe des angegebenen Arrays ist.

Die Speicherplatzkomplexität des obigen Codes ist 1 oder konstant, da wir hier keinen zusätzlichen Speicherplatz verwenden.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um ein Array mithilfe des Block-Swap-Algorithmus um eine bestimmte Anzahl von Drehungen zu drehen. Wir haben den Blockaustauschalgorithmus mithilfe eines iterativen Ansatzes mit O(N)-Zeit und O(1)-Raumkomplexität implementiert, während wir einen rekursiven Ansatz mit O(N)-Raumkomplexität verwendet haben.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm für den Blockaustauschalgorithmus für die Array-Rotation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!