旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为 O(1) 的 原地 算法。

reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数没有返回值．

思路

1. 三旋转法

用基础库函数无脑旋转就行:

1. 第一次旋转，将其反过来
2. 对k要求的部分进行变换
3. 转回来

例： [1, 2, 3, 4, 5, 6, 7] k = 3
先整体旋转 -> [7, 6, 5, 4, 3, 2, 1]
再对前面0~k旋转 -> [5, 6, 7, 4, 3, 2, 1]
最后对后面k~nums.size()旋转 -> [5, 6, 7, 1, 2, 3, 4]

代码：

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

2. 暴力法

遍历一遍取个余然后无脑swap变换

例：[1, 2, 3, 4, 5, 6, 7] k = 3
1. 第一次：[7, 1, 2, 3, 4, 5, 6]
2. 第二次：[6, 7, 1, 2, 3, 4, 5]
3. 第三次：[5, 6, 7, 1, 2, 3, 4]

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        for(int i = 0; i < k % nums.size(); ++i){
            for(int j = nums.size() - 1; j > 0; --j){
                swap(nums[j], nums[j - 1]);
            }
        }
    }
};

Refer

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：OrangeMan
链接：https://leetcode-cn.com/problems/rotate-array/solution/cjian-ji-dai-ma-duo-chong-fang-fa-by-orangeman-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。