题解 | #旋转数组#

旋转数组

http://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042

描述

这是一篇面对初级coder的题解。
知识点：数组 STL中vector的使用
难度：一星

题解

分析：

正常情况下，需要新建数组，先加入后面k=n-m个元素，然后加入前面m个元素即可

本题的坑主要在于当m>n时需要

m = m%n;

为了防止右移的长度大于数组的长度，所以才有取余

操作图解如下

方法一：逐个拼接

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        m = m%n; //为了防止右移的长度大于数组的长度，所以才有取余
        int k=n-m;
        vector<int>ans;//新数组
        for(int i=k;i<n;i++)//从中间开始遍历 逐个加入后面的数
            ans.push_back(a[i]);
        for(int i=0;i<k;i++)//在之后逐个加入前面的数组
            ans.push_back(a[i]);
        return ans;//返回值
        // write code here
    }
};

相当于把旧的数组遍历一遍，逐个加入新数组，

时间复杂度 $O(n)$ 整个数组遍历一遍

空间复杂度 $O(n)$ 开辟等长新数组

运行时间3ms 占用内存424KB

方法二：数组整体拼接

可以采用vector自带的方法，完成对数组的整体拼接

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        m = m%n; //为了防止右移的长度大于数组的长度，所以才有取余
        int k=n-m;//数组长n 把v分成前面k个和后面的m个，
        vector<int>ans;//新数组
        ans.resize(n);//长度为n
        //返回后面的m个数,v本身只留k个
        copy(a.begin()+k,a.end(),ans.begin());
        a.resize(k);
        //将前面的k个拼在后面
        copy(a.begin(),a.end(),ans.begin()+m);
        //返回新数组
        return ans;
        // write code here
    }
};

运行时间： 2 ms 占用内存：404K
由于采用是vector的库函数，实现数组的整块复制。所以时间复杂度是 $O(n)$ ，时间有优化但不是 $O(1)$

同时由于开辟了等长的新数组故最坏情况空间复杂度 $O(n)$

如果用python实现的话，可以直接在原数组上拼接

class Solution:
    def solve(self , n , m , a ):
        # 为了防止右移的长度大于数组的长度，所以才有取余
        m = m % n
        # 交换移动数组
        a[:m], a[m:] = a[-m:],a[:n-m]
        return a

时间复杂度是实现数组的整块移动采用指针操作故为 $O(1)$

直接在原数组上拼接空间复杂度 $O(1)$

不过python的执行效率比较低

运行时间50ms 占用内存7024KB