資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++陣列旋轉的塊交換演算法
塊交換演算法是一種用於陣列旋轉的高效演算法。它可以在O(n)的時間複雜度內完成工作。
因此，在陣列旋轉中，我們得到一個大小為n的陣列arr[]和一個數字k，該數字定義了要旋轉的元素數量。
讓我們來看一個數組旋轉的例子：
輸入：
arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (number of rotations.)輸出：
{1, 8, 9, 2, 4, 6}解釋：旋轉時，我們將一個元素移到最後位置，並將其餘元素向左移動一位。
索引0處的元素將被移到索引n-1。其餘元素將移到前一個索引。
塊交換演算法
塊交換演算法用於完美地執行陣列旋轉。
演算法
步驟1：將陣列分成兩個子陣列，k作為分界點。令它們為X = arr[0...k-1]和Y = arr[k...n-1]。
步驟2：直到X和Y的大小相等，重複以下步驟。
步驟2.1：如果X的大小>Y的大小，則將X分成兩部分X1和X2，使得X1的大小等於Y的大小。然後交換子陣列X1和Y。這將改變原始陣列的結構，從X1X2Y變為YX2X1。
步驟2.2：如果Y的大小>X的大小，則將Y分成兩部分Y1和Y2，使得Y2的大小等於X的大小。然後交換子陣列X和Y2。這將改變原始陣列的結構，從XY1Y2變為Y2Y1X。
步驟3：當X和Y的大小相同時，交換它們。
此演算法需要重複呼叫相同的程式碼塊。此重複呼叫可以使用兩種方法實現。它們是**遞迴方法**和**迭代方法**。我們將使用程式來討論這種方法。
示例
演示遞迴方法的程式：
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, intk){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgo(int arr[], int k, int n) {
if(k == 0 || k == n)
return;
if(k<(n-k)) {
swapSubArray(arr, 0, (n-k), k);
blockSwapAlgo(arr, k, (n-k));
}
else if(k>(n-k)){
swapSubArray(arr, 0, k, (n-k));
blockSwapAlgo((arr+n-k), (2*k-n), k);
}
else{
swapSubArray(arr, 0, (n-k), k);
return;
}
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgo(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
}輸出
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1
示例
演示迭代方法的程式：
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, int k){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgoIt(int arr[], int k, int size) {
int i, j;
if(k == 0 || k == size)
return;
i = k;
j = size - k;
while (i != j) {
if(i < j){
swapSubArray(arr, k-i, k+j-i, i);
j -= i;
}
else{
swapSubArray(arr, k-i, k, j);
i -= j;
}
}
swapSubArray(arr, k-i, k, i);
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgoIt(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
}輸出
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1
更新於：2020年8月5日
1K+瀏覽量
廣告