Algorithm gymnastics 5

Rotate Array

Description

When two arguments, an integer type array and an integer N (rotation speed), are passed, the elements of the array are moved N times (minus to the left, plus to the right). Let's make it a rotated array.

Example

Suppose the following array is passed. If the rotation speed N is -1, all the elements are shifted to the left one by one. If the number of revolutions N is 2, all the elements are shifted to the right one by one twice.

Try It Yourself (Brute Force) The first thing that came to my mind on this issue was the brute force algorithm after rotation Two partial arrays on the left and right will always appear, so make those two arrays. (In the case of N = 2 in the example, left_sub_array = {9, 40} and right_sub_array = {1, 10, 20, 0, 59, 86, 32, 11}) Then, the rotated elements stored in the left and right partial arrays are sequentially updated to the original array. If N is negative, allow left rotation to be applied to the right rotation algorithm.

Runtime Complexity O (n)

Spatial complexity (Memory Complexity) O (n)

Implementation

TEST

OUTPUT

Review

In order to change the order of the elements, it is necessary to rearrange the positions of all the elements, so the execution time O (n) is the limit. However, the amount of spatial complexity can be O (1). That is, it uses only the passed data structure.

Optimization: Memory Complexity O (n)-> O (1)

1. Invert the elements of the original array.
2. Invert the elements from 0 to N-1.
3. Invert the elements from N to Length-1

Example

Suppose the same array as in the previous example is passed. The number of rotations is N = 2.

1. First, invert all the elements of the original array.
2. Then invert the elements from index 0 to N-1 (2-1 = 1).
3. Finally, invert the elements from N (2) to the end of the array. Now the space complexity can be optimized with the constant O (1).

Implementation

OUTPUT (same TEST code)