关关的刷题日记12 – Leetcode 189. Rotate Array 方法1、2、3

题目

Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

题目给出数组的长度和旋转次数，要求对整个数组向右进行旋转操作。

方法1：暴力求解，每次往右移动一步，时间复杂度为O(n2)，超时了。

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

方法2：额外开辟个数组，把旋转后得到的结果算出来一次性存到里面，然后再替换原来数组。时间复杂度O(n).

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k=k%n;
        if(k==0)
            return;
        vector<int>temp(n, 0);
        for(int i=0; i<n; i++)
        {
            temp[(i+k)%n]=nums[i];
        }
        for(int i=0; i<n; i++)
        {
            nums[i]=temp[i];
        }
    }
};

方法3：时间复杂度O(n)，还不需要开辟额外空间，不过不容易想到，可以记下来这种方法。三次翻转法，第一次翻转全部，第二次翻转前k个，第三次翻转后n-k个。

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end)
    {
        for(int i=start; i<=(start+end)/2; i++)
        {
            int temp=nums[i];
            nums[i]=nums[start+end-i];
            nums[start+end-i]=temp;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int n=nums.size(), temp=0;
        k=k%n;
        if(k==0)
            return;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);         
    }
};

方法4：师父出手，总能写出简洁优雅的代码。时间复杂度O(n). C++容器的insert()函数有以下三种用法: 最终*it=val;
//用法1:在指定位置it前“插入”值为val的元素,返回指向这个元素的迭代器,
iterator insert( iterator it, const TYPE &val );

//用法2:在指定位置it前“插入”num个值为val的元素
void insert( iterator it, size_type num, const TYPE &val );

//用法3:在指定位置it前“插入”区间[start, end)的所有元素.
void insert( iterator it, input_iterator start, input_iterator end ); vector中插入一个元素时间复杂度是O(n), 批量插入的话时间复杂度也是O(n).

class Solution {
public:   
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k%=n;
        nums.insert(nums.begin(), nums.begin()+n-k, nums.end());
        nums.resize(n);
    }
};

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。