旋转数组

给定一个数组,将数组中的元素向右移动 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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。