将长度为n数组循环右移k(范围1到n)位

方法一

思考：

1. 找每个元素a[i]的最终所在位置，直接放上去，但是放上去前需要先将放置位置元素保存，然后找被保存元素的最终所在位置...一直循环到a[i]结束。
   为了提高效率，可以倒着处理，这样元素a[i]只需要暂存一次。将a[i]暂存，到最终要放到i位置的元素a[j]放到i位置，再找最终要放到j位置的元素...一直循环到a[i]结束。
2. 1步骤需要循环的次数计算方法。如果n能整除k，则循环k次，否则循环n % k次。

例如，对于1 2 3 4 5 6来说，如果k = 4
则循环6 % k = 2次
第一次处理：1 5 3 (1)
第二次处理：2 6 4 (2)

方法二

以上算法每个元素都只移动了一次，所以时间复杂度是O(n)。因为每个元素有且只移动了一次，所以也可以用移动次数来计算大循环终止条件，这个就无需精确控制循环次数。

方法三

将arr分成两段arr1和arr2，长度分别是n-k和k，将arr1和arr2分别翻转，再将整个arr翻转。

int getPreIndex(int n, int cur, int k)
{
    return (cur + n - k) % n;
}

void moveright(vector<int> &arr, int k)
{
    int num;
    if (arr.size() % k == 0)
    {
        num = k;
    }
    else
    {
        num = arr.size() % k;
    }
    
    for (int i = 0; i < num; i++)
    {
        int tmp = arr[i];
        int curIndex = i;
        int preIndex = getPreIndex(arr.size(), curIndex, k);
        while (preIndex != i)
        {
            arr[curIndex] = arr[preIndex];
            curIndex = preIndex;
            preIndex = getPreIndex(arr.size(), curIndex, k);
        }
        
        arr[curIndex] = tmp;
    }
}

int main()
{
    srand(time(0));
    vector<int> arr(10);

    iota(arr.begin(), arr.end(), 0);
    for (auto &e : arr) cout << e << "\t";
    cout << endl;
    
    moveright(arr, 1);
    for (auto &e : arr) cout << e << "\t";
    cout << endl;
    return 0;
}