数据结构
网络
关系数据库管理系统 (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+浏览量
广告