题目描述

给定一个数组，每次将数组最后一个数移到数组的开头，重复 $k$ 次，$k$ 是非负整数。

注意：

• 请尝试使用不同算法，至少写出3种；
• 能否使用原地算法，即仅使用额外 $O(1)$ 的空间？

样例1

输入：[1,2,3,4,5,6,7] and k = 3
输出：[5,6,7,1,2,3,4]
解释：
移动一次后的结果: [7,1,2,3,4,5,6]
移动两次后的结果: [6,7,1,2,3,4,5]
移动三次后的结果: [5,6,7,1,2,3,4]

样例2

输入：[-1,-100,3,99] and k = 2
输出：[3,99,-1,-100]
解释：
移动一次后的结果：[99,-1,-100,3]
移动两次后的结果：[3,99,-1,-100]

算法

(操作分解，数组翻转) $O(n)$

这道题目的做法有很多种，我们仅给出一个复杂度最优的做法。

这道题目的数据比较坑，$k$ 可能非常大，超出数组长度，所以我们要先将 $k$ 对数组长度取模。

然后可以将数组的旋转操作分解为三次翻转操作：

1. 将整个数组翻转；
2. 将前k个数翻转；
3. 将后 $n - k$ 个数翻转，其中 $n$ 是数组长度；

空间复杂度分析：所有翻转操作均基于交换两个数的操作：swap()，该函数仅使用一个额外的变量，所以整个程序仅使用额外 $O(1)$ 的空间。
时间复杂度分析：总共3次翻转操作，数组中的每个数总共被遍历两次。所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};