Rotate Array
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.
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.
TEST
OUTPUT
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.
Suppose the same array as in the previous example is passed. The number of rotations is N = 2.
Recommended Posts