设数组为 A[0:n−1] 。

方法一：使用辅助数组

我们可以利用数组随机访问的性质，使用辅助数组来将每个元素放至正确的位置。遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i−p)modn 的位置，最后将新数组拷贝至原数组即可。

但要注意，C或C++或Java语言中，负数取模的结果小于等于0，例如 (-1) % 3 返回 -1 而不是 2，当 i−p<0 时以对 i−p 模 n 的结果为下标访问数组可能导致数组越界，所以在取模运算前加上一个数组长度 n 。

C代码如下（含测试用例）：

#include <stdio.h>

void rotate(int* a, int n, int p) {
    int newArr[n];
    for (int i = 0; i < n; i++) {
        newArr[(i - p + n) % n] = a[i];
    }
    for (int i = 0; i < n; i++) {
        a[i] = newArr[i];
    }
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    rotate(a, 5, 2);
    for (int i = 0; i < 5; i++) {
        printf("%d", a[i]);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

void rotate(vector<int>& a, int p) {
    int n = (int)a.size();
    vector<int> newArr(n);
    for (int i = 0; i < n; ++i) {
        newArr[(i - p + n) % n] = a[i];
    }
    for (int i = 0; i < n; ++i) {
        a[i] = newArr[i];
    }
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    rotate(a, 2);
    for (int i = 0; i < 5; i++) {
        cout << a[i];
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。总共遍历两遍数组。
• 空间复杂度： O(n) 。开辟大小为 n 的辅助数组。

方法二：环状替换

我们从位置0开始，最初令 temp=A[0] 。根据规则，位置 0 的元素会放至 (0−p)modn 的位置，令 x=(0−p)modn ，此时交换 temp 和 A[x] ，完成位置 x 的更新。然后，我们考察位置 x ，并交换 temp 和 A[(x−p)modn] ，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0 。

由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为 a 圈；再设该过程总共遍历了 b 个元素。因此，我们有 an=bp ，即 an 一定为 n 和 p 的公倍数。又因为我们在第一次回到起点时就结束，因此 a 要尽可能小，故 an 一定为 n 和 p 的最小公倍数 lcm(n,p) ，其中 lcm 表示最小公倍数。 b=lcm(n,p)/p 。

每轮遍历访问 b=lcm(n,p)/p 个元素，需要 n/b=gcd(n,p) 轮才能遍历所有元素，其中 gcd 表示最大公约数。

C代码如下（含测试用例）：

#include <stdio.h>

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void rotate(int* a, int n, int p) {
    int count = gcd(p, n);
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = a[start];
        do {
            int next = (current - p + n) % n;
            swap(&a[next], &prev);
            current = next;
        } while (start != current);
    }
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    rotate(a, 5, 2);
    for (int i = 0; i < 5; i++) {
        printf("%d", a[i]);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void rotate(vector<int>& a, int p) {
    int n = (int)a.size();
    int count = gcd(p, n);
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = a[start];
        do {
            int next = (current - p + n) % n;
            swap(a[next], prev);
            current = next;
        } while (start != current);
    }
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    rotate(a, 2);
    for (int i = 0; i < 5; i++) {
        cout << a[i];
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。数组中每个元素被遍历一次。
• 空间复杂度： O(1) 。使用常数个辅助变量。

方法三：数组翻转

我们可以先将所有元素翻转，这样尾部的 n−p 个元素就被移至数组头部，然后我们再翻转 A[0:n−p−1] 和 A[n−p:n−1] 即能得到最后的答案。

C代码如下（含测试用例）：

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void reverse(int* a, int start, int end) {
    while (start < end) {
        swap(&a[start], &a[end]);
        start += 1;
        end -= 1;
    }
}

void rotate(int* a, int n, int p) {
    reverse(a, 0, n - 1);
    reverse(a, 0, n - p - 1);
    reverse(a, n - p, n - 1);
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    rotate(a, 5, 2);
    for (int i = 0; i < 5; i++) {
        printf("%d", a[i]);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

void reverse(vector<int>& a, int start, int end) {
    while (start < end) {
        swap(a[start], a[end]);
        start += 1;
        end -= 1;
    }
}

void rotate(vector<int>& a, int p) {
    int n = (int)a.size();
    reverse(a, 0, n - 1);
    reverse(a, 0, n - p - 1);
    reverse(a, n - p, n - 1);
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    rotate(a, 2);
    for (int i = 0; i < 5; i++) {
        cout << a[i];
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。数组中每个元素被交换两次。
• 空间复杂度： O(1) 。使用常数个辅助变量。