题解 | #旋转数组#
旋转数组
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
}
};
相当于把旧的数组遍历一遍，逐个加入新数组，
时间复杂度 )
整个数组遍历一遍
空间复杂度 开辟等长新数组
运行时间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的库函数，实现数组的整块复制。所以时间复杂度是
同时由于开辟了等长的新数组 故最坏情况 空间复杂度
如果用python实现的话，可以直接在原数组上拼接
class Solution: def solve(self , n , m , a ): # 为了防止右移的长度大于数组的长度，所以才有取余 m = m % n # 交换移动数组 a[:m], a[m:] = a[-m:],a[:n-m] return a时间复杂度 是实现数组的整块移动 采用指针操作 故为
直接在原数组上拼接 空间复杂度)
不过python的执行效率比较低
运行时间50ms 占用内存7024KB
总结
stl标准库提供的库函数往往执行效率比较高，不同的语言逻辑和执行效率也不一致
阿Q的题解 文章被收录于专栏
阿Q秋招刷过的题
