Rotate the array
The article sweeps array basics
Rotation array is divided into left rotation and right rotation of two types, force button 189 is entitled right rotation, today share for left rotation.
Given an array, rotate the elements of the array to the left by k positions, where k is non-negative.
<p align=’center’> <p align=’center’> </p>
Arr [] = [1,2,3,4,5,6,7] Arr [] = [3,4,5,6,7,1,2] Arr [] = [1,2,3,4, 4,5,6,7,1] Arr [] = [3,4,5,6,7,1]
I recommend that you do 189 right rotation of an array problem.
Method 1 (temporary array)
Arr [] = [1,2,3,4,5,6,7]; Arr [] = [1,2,3,4,5,6,7]; Arr [] = [1,2,3,4,5,6,7]; Arr [] = [3,4,5,6,7,6,7] Arr [] = [3,4,5,6,7] Arr [] = [1,2] Arr [] = [3,4,5,6,7] Arr [] = [3,4,5,6,7] Arr [] = [3,4,5,6,7] Arr [] = [3,4,5,6,7] Arr [] Arr [] = [3,4,5,6,7,1,2] Arr [] = [3,4,5,6,7,1,2] Arr [] = [3,4,5,6,7,1,2]
<p align=’center’> </p
PS: Pay attention to the subscript boundary conditions when writing code.
void rotationArray(int* arr, int k, int n) { int temp[k]; // temporary array int I,j; Temp (I = 0; temp (I = 0; I = 0; i < k; i++) { temp[i] = arr[i]; } // 2. Move the rest of the array forward k for(I = 0; i < n-k; i++) { arr[i] = arr[i+k]; } for(j = 0;} for(j = 0; j < k; j++) { arr[i++] = temp[j]; }}Complexity analysis
- $O(n)$, where n represents the length of the array.
- Space complexity: $\Theta(k)$, k represents the number of positions of the left-handed.
Method 2 (step-by-step movement method)
Steady is moving step by step according to the definition of left rotation.
For the first rotation, save arr[0] to a temporary variable temp, then move the elements in arr[1] to arr[0], arr[2] to arr[1],… , and so on, and finally, the TEMP is stored in the ARR [n-1].
Arr [] = {1,2,3,4,5,6,7}, k = 2. We rotate the array twice
Arr [] = {2,3,4,5,6,7,1};
Arr [] = {3,4,5,6,7,1,2}
The specific steps are shown in Figure 2-1.
<p align=’center’> </p
The implementation code
C language implementation
#include<stdio.h> void leftRotate(int[] arr, int k, int n) {int I; #include<stdio.h> void leftRotate(int[] arr, int k, int n); for (i = 0; i < k; i++) { leftRotateByOne(arr, n); } } void leftRotateByOne(int[] arr, int n) { int temp = arr[0], i; for (i = 0; i < n-1; i++) { arr[i] = arr[i+1]; } arr[n-1] = temp; } void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", arr[i]); } int main() {int arr[] = {1,2,3,4,5,6,7}; leftRotate(arr, 2, 7); printArray(arr, 7); return 0; }Java implementation:
class RotateArray { void leftRotate(int arr[], int k, int n) { for (int i = 0; i < k; i++) { leftRotateByOne(arr, n); } } void leftRotateByOne(int arr[], int n) { int temp = arr[0]; for (int i = 0; i < n-1; i++){ arr[i] = arr[i+1]; } arr[n-1] = temp; }}Python implementation:
def leftRotate(arr, k, n):
for i in range(k):
leftRotateByOne(arr, n)
def leftRotateByOne(arr, n):
temp = arr[0];
for i in range(n-1):
arr[i] = arr[i-1]
arr[n-1] = tempIt’s not the implementation that matters, it’s the idea, but you can’t do it without the implementation.
Complexity analysis
- Time complexity: $O(kn)$
- Space complexity: $\Theta(1)$
Method 3 (greatest common divisor method)
This method is an extension of method two, which is to move elements step by step, and this method is to move elements according to the greatest common divisor of n and k.
For example, arr [] =,2,3,4,5,6,7,8,9,10,11,12 {1}, k = 3, n = 12.
Calculate GCD (3,12) = 3, and only need to move 3 rounds to get the result of the array elements rotated to the left k positions.
1: I = 0, temp = arr[I]= arr[0] = 1, move arr[j +k] to arr[j], note that 0 <= j+k < n; I represents the counter for the number of moving wheels, and j represents the array index, as shown in Figure 3-1.
<p align=’center’> <p align=’center’> </p
Round 2: I = 1, temp = arr[1] = 2, move arr[j + 3] to arr[j], where 1 <= j <= 7. As shown in Figure 3-2.
<p align=’center’> <p align=’center’> </p
Round 3: I = 2, temp = arr[2] = 3, move arr[j + 3] to arr[j], where 2 <= j <= 8, as shown in Figure 3-3.
<p align=’center’> <p align=’center’> </p
The implementation code
The C language
#include <stdio.h> // Calculate the largest common divisor of k and n GCD int GCD (int a, int b){if(b == 0){return a; } else{ return gcd(b, a % b); } } void leftRotate(int arr[], int k, int n){ int i,j,s,temp; k = k % n; // reduce unnecessary movement int g_c_d = GCD (k, n); // for(I = 0; i < g_c_d; i++){ temp = arr[i]; Arr [I] to temp j = I; Arr [I] to temp j = I; // 2. Arr [j+k] while(1){s = j+k; Arr [j] if (j+k = n) if (j+k = n) j+k < n s = s-n; if (s == i) break; arr[j] = arr[s]; j = s; } arr[j] = temp; Arr [j]} int main() {Arr [] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; int i; leftRotate(arr, 3, 12); for(i = 0; i < 12; i++){ printf("%d ", arr[i]); } getchar(); return 0; }In the while loop, we move arr[j+k] to arr[j]. For example, in the first move, s changes as shown in Figure 3-4. Note that the processing when s = j+k is out of bounds is compared with the edge boundary value n of the array subscript. If the subscript is out of bounds, s = s-n, and then s == I, then exit the while loop and the move ends:
<p align=’center’> </p> >
Voluntary exercise: Try to simulate the situation of n = 12 and k = 8 by yourself (click the blank area below to see the reference answers after the exercise).
Java implementation code
Void lefTrotate (int arr[], int k, int n) {void lefTrotate (int arr[], int k, int n) { For example, k = 13, n = 12, k = k % n; int i, j, s, temp; // s = j + k; int gcd = gcd(k, n); for (i = 0; i < gcd; I ++) {temp = arr[I]; j = i; while (true) { s = j + k; if (s >= n) { s = s - n; } if (s == i) { break; } arr[j] = arr[s]; j = s; } arr[j] = temp; } } int gcd(int a, int b) { if(b == 0) { return a; } else{ return gcd(b, a % b); } } public static void main(String[] args) { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; RotateArray ra = new RotateArray(); ra.leftRotate(arr, 8, 12); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); }}}Python implementation
def leftRotate(arr, k, n):
k = k % n
g_c_d = gcd(k, n)
for i in range(g_c_d):
temp = arr[i]
j = i
while 1:
s = j + k
if s >= n:
s = s - n
if s == i:
break
arr[j] = arr[s]
j = s
arr[j] = temp
def gcd(a, b):
if b == 0:
return a
else
return gcd(b, a % b)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
n = len(arr)
leftRotate(arr, 3, n)
for i in range(n):
print ("%d" % arr[i], end = " ")Complexity analysis
- $O(n)$
- Space complexity: $\Theta(1)$
Method 4 (Block Switching Method)
Arr [] = [1,2,3,4,5,6,7] where k = 2, n = 7
Set the array arr [0,…, n – 1) contains two pieces of A = arr] [0,…, d – 1, B = arr [d,…, n – 1), Arr [] = [3,4,5,6,7,1,2] is equivalent to swapping A and B, as shown in Figure 4-1.
<p align=’center’ </p align=’center
Step 1: Determine the size of A and B. If the length of A is smaller than that of B, then B is divided into two parts, BL and BR, where the length of BR is equal to the length of A. Swap A and Br, that is, the array ABlBr becomes BrBlA. At this point A has been placed in the correct position, and then recursively process the part of B, as shown in Figure 4-2.
<p align=’center’ </p> <p align=’center
Step 2: Recursively process Part B. At this point, Br in Fig. 4-2 is the new A, and BL is the new B. The size of A and B is judged, and the process is similar to the first step, as shown in Fig. 4-3:
<p align=’center’> <p align=’center’> </p
Step 3: Recursively deal with part B. Br in Figure 4-3 is the new A and BL is the new B. Judge the size of A and B. The length of A is greater than that of B. Divide A into two parts, Al and AR, where the length of Al is equal to the length of B. If you swap AL and B, ALARB becomes BARAL, and B is back in its correct position; Recursive processing A, as shown in Figure 4-4.
<p align=’center’> </p align=’center
Step 4: Process A recursively. In Figure 4-4, Al is the new B, and AR is the new A. In this case, the length of A is equal to the length of B, and A and B can be directly exchanged, as shown in Figure 4-5.
<p align=’center’> </p> > </p
The implementation code
The recursive implementation
C language recursive implementation
Void swap(int arr[], int la, int lb, int d) {int I, temp; void swap(int arr[], int la, int lb, int d) {int I, temp; for(i = 0; i < d; i++) { temp = arr[la+i]; arr[la+i] = arr[lb+i]; arr[lb+i] = temp; } } void leftRotate(int arr[], int k, int n) { if(k == 0 || k == n) return; / / the length of A and B are equal, the exchange of direct exchange A, if B (n, k) = = k {swap (arr. Zero, n - k, k); return; } / / A length less than B, then B divided into Bl and Br, ABlBr - > BrBlA if (k < n - k) {swap (arr. Zero, n - k, k); leftRotate(arr, k, n-k); } else // Swap (arr, 0, k, n-k) {Swap (arr, 0, k, n-k); leftRotate(arr+n-k, 2*k-n, k); } } void printArray(int arr[], int size) { int i; for(i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n "); } int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr, 7); getchar(); return 0; }Note: arr+n-k represents an address value, representing the position of the first element of Ar. Where the array name arr indicates the first address of the first element in the array.
Java recursive implementation code
import java.util.*; Public static void LefTrotate (int arr[], int k, int n) {LefTrotateec (arr, 0, k, n); } public static void LefTrotateEC (int arr[], int I, int k, int n) {public static void LefTrotateEC (int arr[], int I, int k, int n) { Don't need to rotate the if (k = = 0 | | k = = n) return; / / A = = B, swap (A, B) if (n - k = = k) {swap (arr, I, I, n -, k + k); return; } // A < B, swap(A,Br), ablBr -- bb0 BrBlA if(k < n-k) {swap(arr, I, n-k + I, k); leftRotateRec(arr, i, k, n - k); } else // A > B , swap(Al, B), AlArB-->BArAl { swap(arr, i, k, n - k); leftRotateRec(arr, n - k + i, 2 * k - n, k); Public static void printArray(int arr[]) {for(int I = 0; i < arr.length; i++) System.out.print(arr[i] + " "); System.out.println(); } public static void swap(int arr[], int la, int lb, int d) {int I, temp; for(i = 0; i < d; i++) { temp = arr[la+i]; arr[la+i] = arr[lb+i]; arr[lb+i] = temp; } } public static void main (String[] args) { int arr[] = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr); }}Python recursive code implementation
def leftRotate(arr, k, n):
leftRotateRec(arr, 0, k, n);
def leftRotateRec(arr, i, k, n):
if (k == 0 or k == n):
return;
if (n - k == k):
swap(arr, i, n - k + i, k);
return;
if (k < n - k):
swap(arr, i, n - k + i, k);
leftRotateRec(arr, i, k, n - k);
else:
swap(arr, i, k, n - k);
leftRotateRec(arr, n - k + i, 2 * k - n, k);
def printArray(arr, size):
for i in range(size):
print(arr[i], end = " ");
print();
def swap(arr, la, lb, d):
for i in range(d):
temp = arr[la + i];
arr[la + i] = arr[lb + i];
arr[lb + i] = temp;
if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6, 7];
leftRotate(arr, 2, 7);
printArray(arr, 7);Iteration implement
C language iteration code:
void leftRotate(int arr[], int k, int n) { int i, j; if( k == 0 || k == n ) { return; } i = k; j = n - k; while (i ! = j) { if(i < j) // A < B { swap(arr, k-i, j-i+k, i); j -= i; } else { swap(arr, k-i, k, j); i -= j; } } swap(arr, k-i, k, i); }Java language iteration implementation code:
public static void leftRotate(int arr[], int d, int n) { int i, j; if (d == 0 || d == n) return; i = d; j = n - d; while (i ! = j) { if (i < j) { swap(arr, d - i, d + j - i, i); j -= i; } else { swap(arr, d - i, d, j); i -= j; } } swap(arr, d - i, d, i); }Python iteration code:
def leftRotate(arr, k, n): if(k == 0 or k == n): return; i = k j = n - k while (i ! = j): if(i < j): # A < B swap(arr, k - i, k + j - i, i) j -= i else: # A > B swap(arr, k - i, k, j) i -= j swap(arr, k - i, k, i) # A == BComplexity analysis
- $O(n)$
- Space complexity: $\Theta(1)$
Method 5 (Reverse Method)
Inversion method can also be used as a reverse method, the known for the original array arr =,2,3,4,5,6,7 [1], [] sinistral 2 position after array for,4,5,6,7,1,2 [3], so is there any way by the rotating array after get the original array?
First invert [3,4,5,6,7,1,2], as shown in Figure 5-4:
<p align=’center’> Figure 5-1 reverse(arr, 0, n)</p>
Then flip [2,1] over and flip [7,6,5,4,3] over to get the result shown in Figure 5-2:
Figure 5-2 Reverse (arr, 0, k), Reverse (arr,k,n)</p>
The algorithm of left-handed k positions of the array is as follows, as shown in Figure 5-3:
leftRotate(arr[], k, n)
reverse(arr[], 0, k);
reverse(arr[], k, n);
reverse(arr[], 0, n);
<p align=’center’> </p align=’center
The implementation code
#include <stdio.h> void printArray(int arr[], int size); void reverseArray(int arr[], int start, int end); / / sinistral k array position void leftRotate (int arr [], int k, int n) {if (k = = 0 | | k = = n) return; // Array size k = k % n; reverseArray(arr, 0, k - 1); reverseArray(arr, k, n - 1); reverseArray(arr, 0, n - 1); } // printout void printArray(int arr[], int size) {int I; for (i = 0; i < size; i++) printf("%d ", arr[i]); } // Reverse array void reverseArray(int arr[], int start, int end) {int temp; while (start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; }} / / main function int main () {int arr [] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; leftRotate(arr, k, n); printArray(arr, n); return 0; }Complexity analysis
- $O(n)$
- Space complexity: $\Theta(1)$
An algorithm is a way to solve a problem, and there are many ways to solve a problem. The one that suits you is the best one. Learn the algorithm well, and gradually you will find that the way you deal with problems will change, become more efficient and perfect!
2021 is the year of the bull! Don’t forget to check out 189 in Leetcode!
This article is from the public number of programmer Jing Yu:
Historical Articles of Jing Yu