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.
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]
Wir können den Austauschalgorithmus verwenden und das Ergebnis erhalten. Wir werden es im nächsten Abschnitt implementieren.
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.
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);
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.
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.
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);
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.
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!
