
#189. Rotate Array
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.
Hint:
Could you do it in-place with O(1) extra space?
Could you do it in-place with O(1) extra space?
题解:最容易想到的是右移k次,用最容易想到的方法,结果是超时,时间复杂度是O(kn).
class Solution {
public:
void rotate(vector<int>& nums, int k) { int n=nums.size(); while(k--)
{
rightShift(nums);
}
}
void rightShift(vector<int>& nums)
{
int temp=;
temp=nums[nums.size()-];
for(int i=nums.size()-;i>;i--)
{
nums[i]=nums[i-];
}
nums[]=temp;
}
};
只好换三步反转法来做,时间复杂度是O(n),空间复杂度是O(1)
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
k=k%n;
if(k==)
return ; reverseString(nums,,n-k-);
reverseString(nums,n-k,n-);
reverseString(nums,,n-);
}
void reverseString(vector<int>& nums,int from,int to)
{
while(from<to)
{
int temp=nums[from];
nums[from++]=nums[to];
nums[to--]=temp;
}
}
};