Dada una array arr[] de tamaño N e índice D , la tarea es rotar la array por el índice D. Tenemos dos flexibilidades, ya sea para rotarlos hacia la izquierda o hacia la derecha a través de diferentes formas que vamos a explorar implementando todas las formas de rotación en ambas rotaciones.
Maneras:
- Usando una array temporal
- Array que gira recursivamente una por una
- Uso del algoritmo de malabarismo
Rotación a la izquierda de la array
Ilustración:
Input : arr[] = {1, 2, 3, 4, 5}
D = 2
Output : 3 4 5 1 2
Explicación de salida:
- La array inicial [1, 2, 3, 4, 5]
- rotar por primer índice [2, 3, 4, 5, 1]
- rotar por segundo índice [3, 4, 5, 1, 2]
Input : arr[] = {10, 34, 56, 23, 78, 12, 13, 65}
D = 7
Output: 65 10 34 56 23 78 12 13
Forma 1: usar una array temporal
Acercarse:
En este método, simplemente cree una array temporal y copie los elementos de la array arr[] desde 0 hasta el índice (D-1). Después de ese movimiento, el resto de elementos de la array arr[] del índice D a N. Luego, mueva los elementos temporales de la array a la array original.
Input arr[] = [1, 2, 3, 4, 5] D = 2
- Almacene los primeros d elementos en una array temporal: temp[] = [1, 2]
- Desplazar el resto del arr[]: arr[] = [3, 4, 5]
- Almacene los elementos D: arr[] = [3, 4, 5, 1, 2]
Ejemplo:
Java
// Java program to Left Rotate an Array
// by D elements
// Main class
class GFG {
// Method 1
// To left rotate arr[]
// of size N by D
void leftRotate(int arr[], int d, int n)
{
// Creating temp array of size d
int temp[] = new int[d];
// Copying first d element in array temp
for (int i = 0; i < d; i++)
temp[i] = arr[i];
// Moving the rest element to index
// zero to N-d
for (int i = d; i < n; i++) {
arr[i - d] = arr[i];
}
// Copying the temp array element
// in original array
for (int i = 0; i < d; i++) {
arr[i + n - d] = temp[i];
}
}
// Method 2
// To print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Method 3
// Main driver method
public static void main(String[] args)
{
// Creating an object of class inside main()
GFG rotate = new GFG();
// Custom input array
int arr[] = { 1, 2, 3, 4, 5 };
// Calling method 1 and 2 as defined above
rotate.leftRotate(arr, 2, arr.length);
rotate.printArray(arr, arr.length);
}
}
3 4 5 1 2
Complejidad temporal: O(N), Espacio auxiliar: O(D)
Forma 2: rotar uno por uno
Acercarse:
Rotar la array recursivamente uno por un elemento
Input arr[] = [1, 2, 3, 4, 5] D = 21
- Intercambiar arr[0] a arr[1]
- Intercambiar arr[1] a arr[2]
- Intercambiar arr[N-1] a arr[N]
- Repita 1, 2, 3 a D veces
Para rotar en uno, almacene arr[0] en una variable temporal temp, mueva arr[1] a arr[0], arr[2] a arr[1] … y finalmente temp a arr[n-1]
Ilustración:
Tomemos el mismo ejemplo arr[] = [1, 2, 3, 4, 5], d = 2
Rotar arr[] por uno 2 veces
Obtenemos [2, 3, 4, 5, 1] después de la primera rotación y [ 3, 4, 5, 1, 2] después de la segunda rotación.
Ejemplo
Java
// Java program to left rotate an array
// by Rotate one by one
// Main class
class GFG {
// Method 1
// To rotate left by D elements
void leftRotate(int arr[], int d, int n)
{
for (int i = 0; i < d; i++)
leftRotatebyOne(arr, n);
}
// Method 2
// To rotate left one by one
void leftRotatebyOne(int arr[], int n)
{
int i, temp;
temp = arr[0];
for (i = 0; i < n - 1; i++)
arr[i] = arr[i + 1];
arr[i] = temp;
}
// Method 3
// To print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Method 4
// Main driver method
public static void main(String[] args)
{
// Creating object of class inside main()
GFG rotate = new GFG();
// Custom input array
int arr[] = { 1, 2, 3, 4, 5 };
// Calling method to rotate array leftwards
// and later printing the array elements
rotate.leftRotate(arr, 2, arr.length);
rotate.printArray(arr, arr.length);
}
}
3 4 5 1 2
Complejidad de tiempo: O(N * D), Espacio auxiliar: O(1)
Manera 3: usando el algoritmo de malabarismo
Acercarse:
Esta es una extensión del método 2. En lugar de mover uno por uno, divida la array en diferentes conjuntos donde el número de conjuntos sea igual al GCD de n y d y mueva los elementos dentro de los conjuntos.
Si GCD es 1 tal cual para la array de ejemplo anterior (n = 5 y d = 2), entonces los elementos se moverán dentro de un solo conjunto, simplemente comenzamos con temp = arr[0] y seguimos moviendo arr[I+d ] a arr[I] y finalmente almacenar temp en el lugar correcto.
Ejemplo:
Java
// Java program to left rotate an array by d elements
// using Juggling Algorithm
// Main class
class GFG {
// Method 1
// To left rotate arr[] of siz N by D
void leftRotate(int arr[], int d, int n)
{
// To handle if d >= n
d = d % n;
int i, j, k, temp;
int g_c_d = gcd(d, n);
for (i = 0; i < g_c_d; i++) {
// move i-th values of blocks
temp = arr[i];
j = i;
// Performing sets of operations if
// condition holds true
while (true) {
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
// Method 2
// To print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
}
// Method 3
// To get gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// Method 4
// main driver method
public static void main(String[] args)
{
// Creating instance of class inside main() method
GFG rotate = new GFG();
// Custom array elements
int arr[] = { 1, 2, 3, 4, 5 };
// Calling above methods inside main() to
// left rotate and print the array elements
rotate.leftRotate(arr, 2, arr.length);
rotate.printArray(arr, arr.length);
}
}
3 4 5 1 2
Complejidad temporal: O(n), Espacio auxiliar: O(1)
Rotación a la derecha de la array
Ilustración:
Input : arr[] = {1, 2, 3, 4, 5}
D = 2
Output : 4 5 1 2 3
Explicación de salida:
- La array inicial [1, 2, 3, 4, 5]
- rotar primer índice [2, 3, 4, 5, 1]
- girar el segundo índice [3, 4, 5, 1, 2]
- girar el tercer índice [4, 5, 1, 2, 3]
Input: arr[] : {10, 34, 56, 23, 78, 12, 13, 65}
D = 5
Output : 56 23 78 12 13 65 10 34
Forma 1: Usar array temporal
Acercarse:
En este método, simplemente cree una array temporal y copie los elementos de la array arr[] de 0 al índice N – D. Después de ese movimiento, el resto de elementos de la array arr[] del índice D a N. Luego, mueva los elementos temporales de la array a la array original. Es como se ilustra debajo de la ilustración de la siguiente manera:
Input arr[] = [1, 2, 3, 4, 5], D = 2 1) Store the first d elements in a temp array temp[] = [1, 2, 3] 2) Shift rest of the arr[] arr[] = [4, 5] 3) Store back the D elements arr[] = [4, 5, 1, 2, 3]
Ejemplo:
Java
// Java program to rotate an array by D elements
// Main class
class GFG {
// Method 1
// To right rotate arr[] of size N by D
void rightRotate(int arr[], int d, int n)
{
// If arr is rotated n times then
// you get the same array
while (d > n) {
d = d - n;
}
// Creating a temporary array of size d
int temp[] = new int[n - d];
// Now copying first N-D element in array temp
for (int i = 0; i < n - d; i++)
temp[i] = arr[i];
// Moving the rest element to index zero to D
for (int i = n - d; i < n; i++) {
arr[i - n + d] = arr[i];
}
// Copying the temp array element
// in original array
for (int i = 0; i < n - d; i++) {
arr[i + d] = temp[i];
}
}
// Method 2
// To print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
// Printing elements of an array
System.out.print(arr[i] + " ");
}
// Method 3
// Main driver method
public static void main(String[] args)
{
// Creating object of class inside main() method
GFG rotate = new GFG();
// Custom input array
int arr[] = { 1, 2, 3, 4, 5 };
// Calling method1 to rotate array
rotate.rightRotate(arr, 2, arr.length);
// Calling method 2 to print array
rotate.printArray(arr, arr.length);
}
}
4 5 1 2 3
Complejidad temporal: O(N), Espacio auxiliar: O(D)
Forma 2: rotar uno por uno
Enfoque: gire la array recursivamente uno por un elemento
Input arr[] = [1, 2, 3, 4, 5], D = 2
- cambiar arr[N] a arr[N-1]
- cambiar arr[N-1] a arr[N-2]
- cambiar arr[2] a arr[1]
- Repita 1, 2, 3 a D veces
Para rotar por uno, almacene arr[N] en una variable temporal temp, mueva arr[N-1] a arr[N], arr[N-2] a arr[N-1]… y finalmente temp a arr[1 ].
Tomemos el mismo ejemplo arr[] = [1, 2, 3, 4, 5], d = 2
Rotar arr[] por uno 2 veces
Obtenemos [5, 1, 2, 3, 4] después de la primera rotación y [ 4, 5, 1, 2, 3] después de la segunda rotación.
Ejemplo:
Java
// Java Program to Rotating Elements One by One
// Main class
class GFG {
// Method 1
// To right rotate array of size n by d
void rightRotate(int arr[], int d, int n)
{
// Iterating till we want
for (int i = n; i > d; i--)
// Recursively calling
rightRotatebyOne(arr, n);
}
// Method 2
// To rotate array by 1
void rightRotatebyOne(int arr[], int n)
{
int i, temp;
temp = arr[0];
for (i = 0; i < n - 1; i++)
arr[i] = arr[i + 1];
arr[i] = temp;
}
// Method 3
// To print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Method 4
// Main driver method
public static void main(String[] args)
{
// Creating an object of class inside main()
GFG rotate = new GFG();
// Custom input elements
int arr[] = { 1, 2, 3, 4, 5 };
// Calling method 1 and 2
rotate.rightRotate(arr, 2, arr.length);
rotate.printArray(arr, arr.length);
}
}
4 5 1 2 3
Aquí hemos rotado 2 elementos uno por uno si hubiéramos rotado solo un elemento, entonces la array habría sido [2,3,4,5,1]
Complejidad de tiempo: O(N * D), Espacio auxiliar: O(1)
Camino 3: Algoritmo de malabares
Enfoque: Esta es una extensión del método 2. En lugar de mover uno por uno, divida la array en diferentes conjuntos donde el número de conjuntos sea igual al GCD de n y d y mueva los elementos dentro de los conjuntos.
Si GCD es 1 tal cual para la array de ejemplo anterior (n = 5 y d = 2), entonces los elementos se moverán dentro de un solo conjunto, simplemente comenzamos con temp = arr[N] y seguimos moviendo arr[I+d ] a arr[I] y finalmente almacenar temp en el lugar correcto.
Java
// Java Program to Rotate Array Elements
// Using Juggling Algorithm
// Main class
class GFG {
// Method 1
// To right rotate arr[]
// of siz N by D
void rightRotate(int arr[], int d, int n)
{
// To use as left rotation
d = n - d;
d = d % n;
int i, j, k, temp;
int g_c_d = gcd(d, n);
for (i = 0; i < g_c_d; i++) {
// Moving i-th values of blocks
temp = arr[i];
j = i;
while (true) {
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
// Method 2
// To print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
}
// Method 3
// To get gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// Method 4
// Main driver method
public static void main(String[] args)
{
// Creating object of class inside main()
GFG rotate = new GFG();
// Custom input elements
int arr[] = { 1, 2, 3, 4, 5 };
// Calling methods 1 and 2
rotate.rightRotate(arr, 2, arr.length);
rotate.printArray(arr, arr.length);
}
}
4 5 1 2 3
Complejidad temporal: O(n), Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por architsharma755 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA