Leetcode—189.轮转数组【中等】

2023每日刷题（二十一）

Leetcode—189.轮转数组

直接法实现代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        vector<int> arr(len, 0);
        for(int i = 0; i < len; i++) {
            int cur = (i + k) % len;
            arr[cur] = nums[i];
        }
        nums = arr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

运行结果

优化空间复杂度为O(1)实现代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k %= len;
        int count = 0;
        int start = 0;
        int cur = 0;
        while(count < len) {
            cur = start;
            // 存的是当前要向右轮转的元素
            int pre = nums[cur];
            do {
                // 轮转元素新位置
                cur = (cur + k) % len;
                // 新位置上旧元素的值
                int tmp = nums[cur];
                nums[cur] = pre;
                pre = tmp;
                count++;
            }while(cur != start);
            start++;
        }
    }
};
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

运行结果

gcd版本算法思路

如果不理解官方的题解，可以这么看，a是通过(cur + k)%len取余总共走的圈数，而一圈有len个元素，我们把这个拉长，b是通过这种方式(cur + k)%len所遍历的元素个数，k相当于步长。所以an = bk。an必然是n,k的公倍数。

大家可以好好感受一下，最好动笔在纸上画一画。

比方说，数组1 2 3 4 5 6，k=3，根据我们的算法，依次遍历就是1、4、2、5、3、6

所以前面别人推出来直接用gcd来求总共遍历b个元素，即循环总次数

大家喜闻乐见的gcd思想实现代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k %= len;
        int cur = 0;
        int start = 0;
        int cnt = gcd(k, len);
        int digits = 0;
        for(cur = 0; cur < cnt; cur++) {
            int pre = nums[cur];
            do {
                cur = (cur + k) % len;
                swap(pre, nums[cur]);
            }while(cur != start);
            start++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！