Leetcode[189] Rotate Array
16 Nov 2015###Task1 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.
[show hint]
Hint: Could you do it in-place with O(1) extra space?
###Python
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.
"""
N = len(nums)
k %= N
self.reverse(nums, 0, N - k - 1)
self.reverse(nums, N - k, N - 1)
self.reverse(nums, 0, N - 1)
return
def reverse(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
###Java
public class Solution {
public void rot(int[] nums, int s, int e) {
while (s < e) {
int temp = nums[s];
nums[s] = nums[e];
nums[e] = temp;
s++;
e--;
}
}
public void rotate(int[] nums, int k) {
if (nums == null || nums.length < 2) {
return ;
}
k = k % nums.length;
rot(nums, 0, nums.length - k - 1);
rot(nums, nums.length - k, nums.length - 1);
rot(nums, 0, nums.length - 1);
return;
}
}
###Points
以n - k为界，分别对数组的左右两边执行一次逆置；然后对整个数组执行逆置。
- Three steps reverse