189. Rotate Array

  • 23.8%

https://leetcode.com/problems/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?

Related problem: Reverse Words in a String II


https://discuss.leetcode.com/topic/9237/3-line-using-reverse

方法一:三次反转

第一次 全部反转; 第二次反转左边的k个; 第三次右边的n-k个。

注意,cpp的内置reverse函数

我的代码实现:

Oct 14, 2017

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
if(n==0 || k==0)
return;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k%n);
reverse(nums.begin()+k%n, nums.end());
return;
}
};

因为是向右移k位,当移动nums.size()的时候,就与不移动nums.size()是一样的,所以k%=n

1
2
3
4
5
6
7
8
9
class Solution {
public:
void rotate(vector<int> & nums, int k) {
int n = nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k%n);
reverse(nums.begin()+k%n, nums.end());
}
};

https://discuss.leetcode.com/topic/9406/3-lines-of-c-in-one-pass-using-swap

Every swap will put one number into its correct position, so the running time is O(n)

For example,

at first, nums[] is [1,2,3,4,5,6,7], n is 7, k is 3

after first outer loop, nums[] is [4,1,2,3], n is 4, k is 3

after second outer loop, nums[] is [4], n is 1, k is 0

loop ends.

方法二:前k个与最后k个互换,前k个正位了。再处理k+1至最后一位,与前一问题相同,继续前面的方法处理。

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

https://discuss.leetcode.com/topic/9801/summary-of-c-solutions

  1. Make an extra copy and then rotate.

Time complexity: O(n). Space complexity: O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
if(n==0 || k<=0)
return;

vector<int> mycopy(n);
for(int i=0; i<n; i++)
mycopy[i] = nums[i];

for(int i=0; i<n; i++)
nums[(i+k)%n] = mycopy[i];
}
};

python

236ms, 3.89%, June.22th, 2016

https://leetcode.com/discuss/29657/my-simple-python-code

python内置方法

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
while k > 0:
nums.insert(0, nums.pop())
k -= 1

java

https://discuss.leetcode.com/topic/14341/easy-to-read-java-solution

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 %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}

public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
谢谢你,可爱的朋友。