Given an array, rotate the array to the right by k steps, where k is non-negative.
Follow up:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 2 * 10^4- It’s guaranteed that
nums[i]fits in a 32 bit-signed integer. k >= 0
本题要把一个数组向右旋转k步，尽量想出3种方法。
首先，无论什么解法，都先判断一下n是否小于2，如果是的话，不管k是多少，都不必旋转了。其次，执行k%=n，因为移动n的倍数位相当于没移动。
暴力解法是每次保留最后一位数字，然后把前n-1个数往后移动一位，重复操作k次。代码如下：
class Solution {
public:
void rotate(vector<int>& nums, int k)
{
int n = nums.size();
if (n < 2 || k % n == 0)
return;
k %= n;
while (k–) {
int last = nums[n – 1];
int j = n – 2;
while (j >= 0) {
nums[j + 1] = nums[j];
–j;
}
nums[0] = last;
}
}
};本代码提交TLE，过不了最后一个大数据集，因为最坏是O(n^2)复杂度。
稍微高明一点的方法是，先把末尾k位数保存到一个临时数组中，然后一次性把前n-k个数移动到末尾，最后再把临时数组中的数据回帖到原数组开头。完整代码如下：
class Solution {
public:
void rotate(vector<int>& nums, int k)
{
int n = nums.size();
if (n < 2 || k % n == 0)
return;
k %= n;
vector<int> right(nums.begin() + n – k, nums.end());
int i = n – k – 1, j = n – 1;
while (i >= 0)
nums[j–] = nums[i–];
i = 0;
while (i < k) {
nums[i] = right[i];
++i;
}
}
};本代码提交AC，用时29MS。
还可以对上述解法稍加变换，即把末尾k位数保存到临时数组right中，然后把原数组的前n-k个数拼接到right的后面，vector的拼接可以用insert。思路和上述算法是一样的。代码如下：
class Solution {
public:
void rotate(vector<int>& nums, int k)
{
int n = nums.size();
if (n < 2 || k % n == 0)
return;
k %= n;
vector<int> right(nums.begin() + n – k, nums.end());
right.reserve(n);
right.insert(right.end(), nums.begin(), nums.begin() + n – k);
nums = right;
}
};本代码提交AC，用时19MS。
最后还有一种很巧妙的方法，比如题目中的例子，要对1,2,3,4,5,6,7向右旋转3位，我们可以首先对整个数组逆序一下（reverse），编程7,6,5,4,3,2,1，然后再对前k=3，后n-k=4个数分别逆序，得到5,6,7,1,2,3,4，这不就是最终答案吗，很有意思。数组逆序可以直接用STL中的reverse，其实也可以自己实现，就是收尾元素不断交换swap。这种解法是常数空间复杂度、O(n)时间复杂度的，代码如下：
class Solution {
private:
void my_reverse(vector<int>::iterator bg, vector<int>::iterator ed)
{
–ed;
while (bg < ed) {
swap(*bg, *ed);
++bg;
–ed;
}
}
public:
void rotate(vector<int>& nums, int k)
{
int n = nums.size();
if (n < 2 || k % n == 0)
return;
k %= n;
my_reverse(nums.begin(), nums.end());
my_reverse(nums.begin(), nums.begin() + k);
my_reverse(nums.begin() + k, nums.end());
}
};本代码提交AC，用时19MS。