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. Screen Shot 2019-12-18 at 10.24.31.png If the rotation speed N is -1, all the elements are shifted to the left one by one. Screen Shot 2019-12-18 at 10.25.05.png If the number of revolutions N is 2, all the elements are shifted to the right one by one twice. Screen Shot 2019-12-18 at 10.27.40.png

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

Screen Shot 2019-12-18 at 10.54.04.png

TEST Screen Shot 2019-12-18 at 11.29.13.png

OUTPUT Screen Shot 2019-12-18 at 11.30.31.png

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. Screen Shot 2019-12-18 at 11.16.56.png

  1. First, invert all the elements of the original array. Screen Shot 2019-12-18 at 11.18.54.png
  2. Then invert the elements from index 0 to N-1 (2-1 = 1). Screen Shot 2019-12-18 at 11.20.46.png
  3. Finally, invert the elements from N (2) to the end of the array. Screen Shot 2019-12-18 at 11.22.30.png Now the space complexity can be optimized with the constant O (1).

Implementation

Screen Shot 2019-12-18 at 11.34.01.png

OUTPUT (same TEST code)

Screen Shot 2019-12-18 at 11.35.56.png

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm