資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用塊交換演算法進行陣列旋轉的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);
時間和空間複雜度
上述程式碼的時間複雜度為 N，其中 N 是給定陣列的大小。
上述程式碼的空間複雜度為 1 或常數，因為我們在這裡沒有使用任何額外的空間。
結論
在本教程中，我們實現了一個 JavaScript 程式，使用塊交換演算法將陣列旋轉給定的次數。我們已經實現了塊交換演算法的迭代方法，其時間複雜度為 O(N)，空間複雜度為 O(1)，同時遞迴方法的時間複雜度為 O(N)，空間複雜度為 O(N)。
更新於：2023年4月20日
170 次瀏覽
廣告