题解 | 旋转数组

1、解题思路

1. 三次反转法： 将数组分成两部分：前 n-M 个元素和后 M 个元素。反转整个数组。反转前 M 个元素。反转后 n-M 个元素。这样可以得到循环右移 M 个位置后的数组。
2. 直接移动法： 逐个将元素移动到目标位置，但这种方法移动次数较多，效率较低。

显然，三次反转法是最优的，因为它只需要进行三次反转操作，时间复杂度为 O(n)，空间复杂度为O(1)。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        if (n == 0 || m == 0) {
            return a;
        }

        m = m % n;  // 处理 m 大于 n 的情况

        // 反转整个数组
        reverse(a.begin(), a.end());
        // 反转前 m 元素
        reverse(a.begin(), a.begin() + m);
        // 反转后 n-m 个元素
        reverse(a.begin() + m, a.end());

        return a;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        if (n == 0 || m == 0) return a;

        m = m % n; // 处理m大于n的情况

        // 反转整个数组
        reverse(a, 0, n - 1);
        // 反转前m个元素
        reverse(a, 0, m - 1);
        // 反转后n-m个元素
        reverse(a, m, n - 1);

        return a;
    }

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

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 旋转数组
# @param n int整型 数组长度
# @param m int整型 右移距离
# @param a int整型一维数组 给定数组
# @return int整型一维数组
#
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        if n == 0 or m == 0:
            return a
        
        m = m % n  # 处理m大于n的情况
        
        # 反转整个数组
        a.reverse()
        # 反转前m个元素
        a[:m] = reversed(a[:m])
        # 反转后n-m个元素
        a[m:] = reversed(a[m:])
        
        return a

3、复杂度分析

1. 处理m大于n的情况：通过取模运算，确保m在有效范围内（0 ≤ m < n）。
2. 三次反转 ： 反转整个数组：将数组整体反转。反转前m个元素：将前m个元素反转回原来的顺序。反转后n-m个元素：将后n-m个元素反转回原来的顺序。
3. 时间复杂度：O(n)，因为每个元素被访问三次。
4. 空间复杂度：O(1)，没有使用额外的数组空间。