题解 | 旋转数组

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        //取余，因为每次长度为n的旋转数组相当于没有变化
        m = m % n; 
        //第一次逆转全部数组元素
        reverse(a.begin(), a.end()); 
        //第二次只逆转开头m个
        reverse(a.begin(), a.begin() + m); 
        //第三次只逆转结尾m个
        reverse(a.begin() + m, a.end()); 
        return a;
    }
};

1. 计算实际移动距离：由于 M 可能大于数组长度 n，实际有效的移动距离是 M % n
2. 三次反转：反转整个数组 反转前 M 个元素 反转后 N-M 个元素

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，且每个元素只被移动了两次。

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        if (n == 0 || m % n == 0) {
            return a;
        }
        
        m = m % n;  // 计算实际需要移动的距离
        
        // 三次反转法
        reverse(a, 0, n - 1);    // 反转整个数组
        reverse(a, 0, m - 1);    // 反转前m个元素
        reverse(a, m, n - 1);    // 反转剩余元素
        
        return a;
    }
    
private:
    // 辅助函数：反转数组中从start到end的部分
    void reverse(vector<int>& arr, int start, int end) {
        while (start < end) {
            swap(arr[start], arr[end]);
            start++;
            end--;
        }
    }
};