15 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [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]

示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

提示：

• 1 <= $nums.length$ <= $10^5$
• $-2^{31}$ <= nums[i] <= $2^{31}$ -1
• 0 <= k <= $10^5$

进阶：

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

题解1 环状替换（学习思想）（空间O(1)）

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int s = nums.size();、
        // 先处理k（减少后面的不必要循环）
        k = k % s;
        // cylimit 就是为了保证能把元素全部遍历, 设最小遍历次数为N
        // N = as = bk (等式基于遍历经过的长度)-> N 应该是s, k的最小公倍数lcm(s, k)
        // lcm(s, k)/k = b 即遍历N次遍历过的元素总数目
        // cylimit = s / (1/k * lcm(s, k)) = sk / lcm(s,k) = gcd(s, k) 即s, k最大公倍数  
        int cylimit = gcd(k, s);
        for(int c = 0; c < cylimit; c++){
            // O(1)： 把每个能计算到的位置对应的原来的值放在[c]的位置
            int cur = c;
           do{
               // 新下标
                int newI = (cur+k) % s;
                // 每次都把改变的值放在[c]上
                swap(nums[newI], nums[c]);
                // 循环找下一个
                cur = newI;
            }while(cur != c); // %的关键：停止条件是回到起始位置
        }

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

题解2 翻转数组（有意思好理解）（空间O(1)）

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end){
        while(start < end){
            swap(nums[start], nums[end]);
            start ++;
            end --;
        }
    }
    void rotate(vector<int>& nums, int k) {
        const int s = nums.size();
        // 先处理k（减少后面的不必要循环）
        k = k % s;
        reverse(nums, 0, s-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, s-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题解3 空间O(N)秒答

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int s = nums.size();
        // 先处理k（减少后面的不必要循环）
        k = k % s;
        vector<int> newN(s, 0);
        for(int i = 0; i < s; i++){
            newN[(i+k)%s] = nums[i];
        }
        nums.assign(newN.begin(), newN.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13