PAT 1008 数组元素循环右移问题

题目：数组元素循环右移问题

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A0​A1​⋯AN−1​）变换为（AN−M​⋯AN−1​A0​A1​⋯AN−M−1​）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式:

每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。

输出格式:

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例:

6 2
1 2 3 4 5 6

输出样例:

5 6 1 2 3 4

算法思路

这是一个经典的逆置问题，采用三次逆置即可完成循环右移过程。

例如：ABCDEFG循环右移2位。

1.先将前5位逆置 EDCBA FG

2.再将后2位逆置 EDCBA GF

3.最后将整个数组逆置 FGABCDE

回到该题：将长度为n的数组循环右移m位。

1.先将前 n - m 位逆置

2.再将后 m 位逆置

3.最后将整个数组逆置

注意事项

1.当 m ≥ n - 1 时，reverse中收到的参数为负数，无法得到正确答案。而逆置的效果是周期性的，所以可以将m调整为小于n。

2.reverse函数传递参数数组a时，需要添加引用符号，否则只对形参逆置。

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

// 定义一个reverse函数，逆置a的部分区间
void reverse(vector<int> &a, int l, int r)
{
    // 使用双指针法进行反转
    for (int i = l, j = r; i < j; i++, j--)
        swap(a[i], a[j]);  // 交换i和j位置的元素
}

int main()
{
    // 输入
    int n, m, tag = 0;
    cin >> n >> m;  

    vector<int> a(n);
    for (int i = 0; i < n; i++)    
        cin >> a[i];  

    // 由于m可能大于n，因此当m大于或等于n时，循环减去n，直到m小于n
    while (m >= n)
        m -= n;
    
    // 逆置前n-m个元素
    reverse(a, 0, n - m - 1);
    // 逆置后m个元素
    reverse(a, n - m, n - 1);
    // 逆置整个数组
    reverse(a, 0, n - 1);

    // 输出循环右移后的数组
    for (int i = 0; i < n; i++)
    {
        if (tag == 0)    
            tag = 1;  // 第一个元素前不加空格
        else    
            cout << " ";  // 后续元素之间加空格

        cout << a[i];  // 输出元素
    }
    return 0;
}