## 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.

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?

### Analysis:

1st solution is to use a temp array. Space O(n).e.g. nums = [ 1 2 3 4 5 ], k=2

temp = [4 5 1 2 3]

num = temp

2nd solution is to rotate one position each time and do it k times. Space O(1), but it will exceed the time limit.

e.g. nums = [1 2 3 4 5], k=2

1st iteration:

nums = [1 1 2 3 4] temp = 5, then nums = [5 1 2 3 4]

2nd iteration:

nums = [5 5 1 2 3] temp = 4, nums = [4 5 1 2 3]

3rd solution is to rotate k steps once for an element. Space O(1).

e.g. nums = [1 2 3 4 5 6], k=2

1st iteration: starts from nums[i=0], keep rotate nums[i+k] until meet the start position

nums = [

__5__2

__1__4

__3__6]

2nd iteration: starts from nums[i=1]

nums = [5

__6__1

__2__3

__4__]

How to determine the number of iterations?

Use the gcd (greatest common divisor) between n and k. Because we need to find how many "circles" are there in the sequence, one circle is like counting each element nums[i] + k + k + k... and back to nums[i]. If the gcd is 1, which means only one circle will cover all the elements in the sequence, so only 1 iteration is needed.If the gcd is 2, there are 2 circles, so 2 iterations are needed.

### Code(C++):

class Solution { public: int gcd(int a, int b){ if (b==0){ return a; }else{ return gcd(b, a%b); } } void rotate(int nums[], int n, int k) { int i,j,tmp,pre; k = k%n; for (int i=0;i<gcd(n,k);i++){ pre = nums[i]; j=i; while ((j+k)%n != i){ tmp = nums[(j+k)%n]; nums[(j+k)%n] = pre; pre = tmp; j = (j+k)%n; } nums[(j+k)%n] = pre; } } };

### Code(Python):

class Solution: # @param nums, a list of integer # @param k, num of steps # @return nothing, please modify the nums list in-place. def rotate(self, nums, k): def gcd(a,b): if b==0: return a else: return gcd(b, a%b) n = len(nums) for i in range(gcd(n,k)): pre = nums[i] j = i while (j+k)%n != i: nums[(j+k)%n], pre = pre, nums[(j+k)%n] j = (j+k)%n nums[(j+k)%n] = pre

## No comments:

## Post a Comment