1008 数组元素循环右移问题 (20 分)

### 回答1：
题目描述

给定一个长度不超过 100 的正整数序列，要求对这个序列进行循环右移操作。即将序列的最后一个元素移到第一个位置，其他元素依次向后移动一个位置。例如，将序列 {1, 2, 3, 4, 5} 循环右移一次得到序列 {5, 1, 2, 3, 4}。

输入格式

输入第一行给出正整数 N（≤100）和正整数 M（≤N），分别为序列长度和循环右移的次数。第二行给出 N 个正整数，即待循环移的序列，每个数不超过 100。

输出格式

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

输入样例

5 2
1 2 3 4 5

输出样例

4 5 1 2 3

思路分析

将数组的后 M 个元素移到数组的前面，再将前面的元素移到数组的后面。

代码实现

### 回答2：
这道题目要求将给定数组循环右移k次，也就是将数组的最后k个元素移到数组的前k个位置。我们可以使用反转数组的方式来解决这个问题，具体步骤如下：

1. 首先将整个数组反转；
2. 将前k个元素反转；
3. 将剩余的n-k个元素反转。

这样操作之后，数组就完成了k次右移的操作。

为什么这种做法是正确的呢？我们可以根据下图来分析：

假设数组为[1, 2, 3, 4, 5, 6, 7]，我们要将其循环右移3次。
1. 我们首先将整个数组反转，得到[7, 6, 5, 4, 3, 2, 1]；
2. 然后将前3个元素反转，得到[5, 6, 7, 4, 3, 2, 1]；
3. 最后将剩余的4个元素反转，得到[5, 6, 7, 1, 2, 3, 4]。

可以发现，这个结果就是原数组右移3位之后的结果。原来的[1, 2, 3, 4, 5, 6, 7]的最后3个元素[5, 6, 7]移动到了最前面，而原来的前4个元素[1, 2, 3, 4]被移动到了数组的最后面。这就是我们想要的结果。

总的来说，这个算法的时间复杂度是O(n)，空间复杂度是O(1)，非常高效。因此，相比于暴力法，使用反转数组的方式是一个更好的解决方案。

### 回答3：
问题描述

给定一个长度为 $N$ 的整型数组 $A$，要求把 $A$ 中的元素循环右移 $M$ 个位置。即将 $A$ 中的元素从后往前依次取出放在数组最前面，直到所有元素都被移位为止。

解决方法

解决这个问题的方法有很多种，下面列举其中两种方法。

方法一：暴力枚举

最简单直接的方法就是按照题意模拟，将数组 $A$ 的元素循环右移 $M$ 个位置。具体实现思路如下：

- 给定数组 $A$ 和循环右移的次数 $M$；
- 循环 $M$ 次，每次循环将数组 $A$ 的最后一个元素放在数组的第一个位置；然后将数组 $A$ 中的所有元素向后移动一位（除了第一个元素）；
- 循环结束后，数组 $A$ 就被循环右移了 $M$ 个位置。

这种方法的时间复杂度是 $O(NM)$，如果 $N$ 和 $M$ 均较大时，运行效率较低。

方法二：三次翻转

通过分析数组循环右移的本质，可以发现循环右移实际上是对数组的三段子序列翻转（参考反转字符串题目）。具体实现思路如下：

- 给定数组 $A$ 和循环右移的次数 $M$；
- 将数组 $A$ 的前 $N-M$ 个元素翻转；
- 将数组 $A$ 的后 $M$ 个元素翻转；
- 最后将整个数组 $A$ 翻转，得到循环右移 $M$ 个位置后的结果。

这种方法的时间复杂度是 $O(N)$，因此是一种更优秀的解决方法。

代码示例

下面给出方法二的代码示例：

void reverse(int* nums, int start, int end) {
while(start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}

void rotate(int* nums, int numsSize, int k) {
k = k % numsSize;
reverse(nums, 0, numsSize - k - 1);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize - 1);
}

这段代码中，reverse 函数用于将 nums 数组中下标从 start 到 end 的元素翻转；rotate 函数用于将 nums 数组中的元素循环右移 k 个位置。此外，k 可能比数组的长度大，所以需要先对 k 取模。