方法（一种杂耍算法）将数组分成不同的集合，其中集合的数量等于n和d的GCD，并在集合中移动元素 . 如果GCD对于上面的示例数组（n = 7和d = 2）是1，那么元素将仅在一个集合内移动，我们只是从temp = arr [0]开始并继续移动arr [I d]到arr [I]并最终将temp存储在正确的位置 .
这是n = 12和d = 3的例子.GCD是3和
设arr []为{1,2,3,4,5,6,7,8,9,10,11,12}
a）元素首先在第一组中移动 - （参见下图中的此运动）
ArrayRotation
arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}
b）然后在第二组 . arr []在此步骤之后 - > {4 5 3 7 8 6 10 11 9 1 2 12}
c）最后在第三组 . arr []在此步骤之后 - > {4 5 6 7 8 9 10 11 12 1 2 3} / 函数打印数组 / void printArray（int arr []，int size）;
/*Function to get gcd of a and b*/
int gcd(int a,int b);
/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int d, int n)
{
int i, j, k, temp;
for (i = 0; i < gcd(d, n); i++)
{
/* move i-th values of blocks */
temp = arr[i];
j = i;
while(1)
{
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
printf("%d ", arr[i]);
}
/*Function to get gcd of a and b*/
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
/* Driver program to test above functions */
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
leftRotate(arr, 2, 7);
printArray(arr, 7);
getchar();
return 0;
}
时间复杂度：O（n）辅助空间：O（1）
有人可以给我很好的解释这个算法如何工作及其渐近的复杂性？
1 回答
函数中的for循环：
将进行彻底的迭代
gcd(d, n)迭代 . 现在让我们看看循环中发生了什么：它需要满足所有单元格arr[k]：k % gcd(d, n) == i并交换它们 . 当然，确切地说：n / gcd(d, n)，这是函数在循环的一次迭代中将进行的交换次数 . 因此，函数的整个渐近时间复杂度将是O(gcd(d, n) * n / gcd(d, n)) == O(n). 其余代码对时间复杂度没有影响，并且几乎是自我解释的 .