LeetCode189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

1
2
3
4
5
6
Input: [1,2,3,4,5,6,7] and 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:

1
2
3
4
5
Input: [-1,-100,3,99] and 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]

Note:

  • 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?

Reverse

  • Time complexity : O(n) n个元素翻转3次.
  • Space complexity : O(1)

my code in cpp (two pointers)

这种方法是将数组分成左右两组,分别反转各自的组,最后整个数组翻转.注意这里的k要取模,因为k可能大于size.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void rotate(vector<int>& nums, int k) {
k %= nums.size();

int mid = nums.size() - k;
//翻转左边数组
int l = 0, r = mid - 1;
while (l < r)
swap(nums[l++], nums[r--]);
//翻转右边数组
l = mid, r = nums.size()-1;
while (l < r)
swap(nums[l++], nums[r--]);
//翻转整个数组
l = 0, r = nums.size() - 1;
while (l < r)
swap(nums[l++], nums[r--]);
}

my code in cpp2(STL)

1
2
3
4
5
6
7
void rotate(vector<int>& nums, int k) {
k %= nums.size();
int mid = nums.size() - k;//index
reverse(nums.begin(), nums.begin() + mid);//[,)
reverse(nums.begin() + mid, nums.end());//[,)
reverse(nums.begin(), nums.end());
}

Brute Force[Time Limit Exceeded]

  • Time complexity : O(n∗k). All the numbers are shifted by one step(O(n)) k times(O(k))
  • Space complexity : O(1)

my code in cpp

1
2
3
4
5
6
7
void rotate(vector<int>& nums, int k) { 
while (k--)
{
int _last = nums.size();
while(--_last) swap(nums[_last], nums[_last-1]);
}
}

push_back,erase[Time Limit Exceeded]

my code in cpp

1
2
3
4
5
6
7
8
void rotate(vector<int>& nums, int k) {
k %= nums.size();
for(;k>0;k--)
{
nums.insert(nums.begin(), nums.back());
nums.erase(nums.end()-1);
}
}

总结

1


其它参考方法

法4.下面这种方法其实还蛮独特的,通过不停的交换某两个数字的位置来实现旋转,根据网上这个帖子的思路改写而来,数组改变过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (nums.empty()) return;
int n = nums.size(), start = 0;
while (n && (k %= n)) {
for (int i = 0; i < k; ++i) {
swap(nums[i + start], nums[n - k + i + start]);
}
n -= k;
start += k;
}
}
};

法5.Using Cyclic Replacements [Accepted]

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int count = 0;
for (int start = 0; count < nums.length; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % nums.length;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start != current);
}
}
}

Complexity Analysis

  • Time complexity : O(n)
  • Space complexity : O(1)
Thanks for Support.