Алгоритм жонглирования относительно вращения правой матрицы

Question

Недавно я узнал о вращении массива за линейное время, используя алгоритм жонглирования. Вот фрагмент относительно левого поворота массива.

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)

(Я решил этот вопрос, используя метод грубой силы и метод обращения).

Answer 1

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 из условия l oop. Технически это не влияет на сложность, но достаточно вычислить gcd только один раз.

Чтобы повернуть массив k раз вправо, просто поверните его n - k раз влево.

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

Или измените 8-ю строку на d = (j - k + n) % n;

Answer 2

Не уверен, что вы делаете это как интеллектуальное упражнение или для производственного кода, но для производственного кода используйте алгоритм STL rotate:

#include<iostream>
#include<algorithm>

using namespace std;

void display(int* a, int length)
{
    for (int i = 0; i < length; ++i)
        cout << a[i] << " ";

    cout << endl;
}

int main()
{
    const int len = 5;

    int arr[] =  { 1,2,3,4,5 };

    display(arr, len);

    rotate(arr, arr + 1, arr + len); // arr + x means left by x

    display(arr, len);

    rotate(arr, arr + len - 1, arr + len); // arr + len - x means right by x 

    display(arr, len);
}