Leetcode 189. 旋转数组 (C++) （小白学习之路）

水深无声 2023-07-15 13:08 5阅读 0赞

题目描述：

给定一个数组，将数组中的元素向右移动 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\]  
示例 2:

输入: \[-1,-100,3,99\] 和 k = 2  
输出: \[3,99,-1,-100\]  
解释:   
向右旋转 1 步: \[99,-1,-100,3\]  
向右旋转 2 步: \[3,99,-1,-100\]  
说明:

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/rotate-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题本身难度不大，但是因为有很多解法而变得很经典，以下理一理我想到的方法：

1.创建一个新数组（不符合原地旋转的题意）

把原数组的后k位放到新数组的前k位，然后把原数组剩下的数按顺序放入新数组，这就是标准的旋转操作；

这里有一个优化的办法，不需要创建新数组，就是把原数组后K位通过vector的insert函数，insert(nums.begin())，插入到数组前面，然后通过resize()函数把后面多余的位数抹去即可

2.三重旋转

逆序前len-K位，逆序后K位，整体逆序，经典做法，代码如下：

class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
            int len = nums.size();
            k = k%len;
            reverse(nums.begin(),nums.begin()+len-k); //逆序前len-k位
            reverse(nums.end()-k,nums.end());    //逆序后k位
            reverse(nums.begin(),nums.end());    //整体逆序
    
        }
    };

因为逆序有O（n）级别的算法，因此该算法的时间复杂度为O（n）,此方法还有更简洁的rotate方法，属于vector的用法之一，后面学习之后补上

3.最大公约数交替

这是目前最快的算法，标准的时间复杂度O（n）,具体来说的话时间复杂度就是n,上一种3重逆序的时间复杂度是2n（因为其实相当于遍历了两遍数组），这个方法的思路也很简单，向后旋转k位，那么原来位于i的数就到了i+k的位置，只要用一个temp临时储存i+k位置的数，直到i+k回到了最初的i,那么遍历就结束了；

但有一种情况需要考虑，就是数组长度Len与k存在公约数的情况，这个时候无论怎么+K都存在还没有被遍历到的数，举个例子,len==8, k==2， 遍历顺序是0--2--4--6--0， 因此下一次需要遍历的是1--3--5--7，在这里要写一个循环确保每一个公约数下的数都能被遍历到，代码如下：

class Solution {
    public:
        int gcd(int a, int b)     //最大公约数，辗转相除法
        {
            if (a<b) swap(a,b);
            return (b==0)?a:gcd(b,a%b);
        }
        void rotate(vector<int>& nums, int k) {
            int len = nums.size();
            k = k%len;
            if(len<2||!k) return;    //数组长度小于2或者k==0时直接返回
            int gcdab = gcd(len,k);
            for(int i=0;i<gcdab;i++)    //公约数的循环
            {
                int temp = nums[i];    //存起始位置
                int j = i+k;
                while(j%len != i)
                {
                    int temp1 = nums[j];
                    nums[j] = temp;
                    temp = temp1;    //更新上一次的数
                    j = (j+k)%len;
                }
                nums[i] = temp;    //把遍历的最后一个数更新到他应该属于的最初的位置
            }
    
    
        }
    };

测试结果，时间确实是三重旋转的一半，证实了我的猜测。

但是这个方法比较难写，要注意的tricky部分有点多，所以如果不是对速度要求最好，还是建议用三重旋转写，逻辑简单，也不大会出错。

这道题还有很多python语言的一行代码解法，这里就不写了，算法题还是着重在解题的思路上。