时间戳

首页 > 解决方案 > 关于右阵列旋转的杂耍算法

c++ - 关于右阵列旋转的杂耍算法

问题描述

最近，我使用 Juggling 算法了解了线性时间的阵列旋转。这是关于数组左旋转的片段。

void ArrayRotate (int A[], int n, int k)
{
  int d=-1,i,temp,j;
  for(i=0;i<gcd(n,k);i++)
  {
    j=i;
    temp=A[i];
    while(1)
    {
      d=(j+k)%n;
      if(d==i)
        break;
      A[j]=A[d];
      j=d;
    }
    A[j]=temp;
  }
}

但现在我被困在如何使用这种杂耍算法以正确的方向旋转阵列。

1,2,3,4,5  (given array) 
5,1,2,3,4   (after 1 right rotation)

（我已经使用蛮力法和反转法解决了这个问题。）

标签： c++arraysalgorithmdata-structures

解决方案

  1. 如前所述，如果允许，您应该使用 std::rotate 。
  2. 您的实现有一个错误。这是一个固定的实现。
void ArrayRotate(int A[], int n, int k) {
    int d = -1, i, temp, j;
    int g = gcd(n, k);
    for (i = 0; i < g; ++i) {
        j = i;
        temp = A[i];
        while (true) {
            d = (j + k) % n;
            if (d == i) {
                break;
            }
            A[j] = A[d];
            j = d;
        }
        A[j] = temp;
    }
 }

另请注意，我从循环条件中取出了 gcd 计算。它在技术上不会影响复杂性，但只计算一次 gcd 就足够了。

要将数组k向右旋转次数，只需将其n - k向左旋转次数即可。

void ArrayRotateRight(int A[], int n, int k) {
    ArrayRotate(A, n, n - k);
}

或者将第 8 行更改为d = (j - k + n) % n;

推荐阅读