Dada una array de tamaño n y múltiples valores alrededor de los cuales necesitamos rotar la array a la izquierda. ¿Cómo encontrar rápidamente múltiples rotaciones a la izquierda?
Ejemplos:
Input : arr[] = {1, 3, 5, 7, 9}
k1 = 1
k2 = 3
k3 = 4
k4 = 6
Output : 3 5 7 9 1
7 9 1 3 5
9 1 3 5 7
3 5 7 9 1
Input : arr[] = {1, 3, 5, 7, 9}
k1 = 14
Output : 9 1 3 5 7
Enfoque simple: ya hemos discutido diferentes enfoques dados en las publicaciones a continuación.
- Rotación a la izquierda de la array (algoritmos simples y de malabarismo) .
- Algoritmo de intercambio de bloques para la rotación de arrays
- Algoritmo de inversión para la rotación de arrays
El mejor de los enfoques anteriores requiere O(n) tiempo y O(1) espacio adicional.
Enfoque simple: estamos utilizando el algoritmo inverso, pero esta vez para múltiples valores de k; puede hacer clic en el enlace anterior para comprender este enfoque.
Implementación:
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.Arrays;
class GFG {
public static void leftRotate(int[] A, int a, int k)
{
//if the value of k ever exceeds the length of the array
int c = k % a;
//initializing array D so that we always
//have a clone of the original array to rotate
int[] D = A.clone();
rotateArray(D, 0, c - 1);
rotateArray(D, c, a - 1);
rotateArray(D, 0, a - 1);
// printing the rotates array
System.out.print(Arrays.toString(D));
System.out.println();
}
// Function to rotate the array from start index to end index
public static int[] rotateArray(int[] A, int start,
int end)
{
while (start < end) {
int temp = A[start];
A[start] = A[end];
A[end] = temp;
start++;
end--;
}
return A;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 3, 5, 7, 9 };
int n = A.length;
int k = 2;
leftRotate(A, n, k);
k = 3;
leftRotate(A, n, k);
k = 4;
leftRotate(A, n, k);
}
}
Producción
[5, 7, 9, 1, 3] [7, 9, 1, 3, 5] [9, 1, 3, 5, 7]
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Enfoque eficiente:
Los enfoques anteriores funcionan bien cuando se requiere una sola rotación. Los enfoques también modifican la array original. Para manejar múltiples consultas de rotación de arrays, usamos una array temporal de tamaño 2n y manejamos rápidamente las rotaciones.
- Paso 1: copie la array completa dos veces en la array temp[0..2n-1].
- Paso 2: La posición inicial de la array después de k rotaciones en temp[] será k % n. hacemos k
- Paso 3: Imprima la array temp[] de k % n a k % n + n.
Implementación:
C++
// CPP implementation of left rotation of
// an array K number of times
#include<bits/stdc++.h>
using namespace std;
// Fills temp[] with two copies of arr[]
void preprocess(int arr[], int n, int temp[])
{
// Store arr[] elements at i and i + n
for (int i = 0; i<n; i++)
temp[i] = temp[i + n] = arr[i];
}
// Function to left rotate an array k times
void leftRotate(int arr[], int n, int k, int temp[])
{
// Starting position of array after k
// rotations in temp[] will be k % n
int start = k % n;
// Print array after k rotations
for (int i = start; i < start + n; i++)
cout << temp[i] << " ";
cout << endl;
}
// Driver program
int main()
{
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int temp[2*n];
preprocess(arr, n, temp);
int k = 2;
leftRotate(arr, n, k, temp);
k = 3;
leftRotate(arr, n, k, temp);
k = 4;
leftRotate(arr, n, k, temp);
return 0;
}
Java
// Java implementation of left rotation of
// an array K number of times
class LeftRotate
{
// Fills temp[] with two copies of arr[]
static void preprocess(int arr[], int n,
int temp[])
{
// Store arr[] elements at i and i + n
for (int i = 0; i<n; i++)
temp[i] = temp[i + n] = arr[i];
}
// Function to left rotate an array k time
static void leftRotate(int arr[], int n, int k,
int temp[])
{
// Starting position of array after k
// rotations in temp[] will be k % n
int start = k % n;
// Print array after k rotations
for (int i = start; i < start + n; i++)
System.out.print(temp[i] + " ");
System.out.print("\n");
}
// Driver program
public static void main (String[] args)
{
int arr[] = {1, 3, 5, 7, 9};
int n = arr.length;
int temp[] = new int[2*n];
preprocess(arr, n, temp);
int k = 2;
leftRotate(arr, n, k, temp);
k = 3;
leftRotate(arr, n, k, temp);
k = 4;
leftRotate(arr, n, k, temp);
}
}
/*This code is contributed by Prakriti Gupta*/
Python3
# Python3 implementation of left rotation
# of an array K number of times
# Fills temp with two copies of arr
def preprocess(arr, n):
temp = [None] * (2 * n)
# Store arr elements at i and i + n
for i in range(n):
temp[i] = temp[i + n] = arr[i]
return temp
# Function to left rotate an array k times
def leftRotate(arr, n, k, temp):
# Starting position of array after k
# rotations in temp will be k % n
start = k % n
# Print array after k rotations
for i in range(start, start + n):
print(temp[i], end = " ")
print("")
# Driver program
arr = [1, 3, 5, 7, 9]
n = len(arr)
temp = preprocess(arr, n)
k = 2
leftRotate(arr, n, k, temp)
k = 3
leftRotate(arr, n, k, temp)
k = 4
leftRotate(arr, n, k, temp)
# This code is contributed by Sanghamitra Mishra
C#
// C# implementation of left rotation of
// an array K number of times
using System;
class LeftRotate
{
// Fills temp[] with two copies of arr[]
static void preprocess(int []arr, int n,
int[] temp)
{
// Store arr[] elements at i and i + n
for (int i = 0; i<n; i++)
temp[i] = temp[i + n] = arr[i];
}
// Function to left rotate an array k time
static void leftRotate(int []arr, int n, int k,
int []temp)
{
// Starting position of array after k
// rotations in temp[] will be k % n
int start = k % n;
// Print array after k rotations
for (int i = start; i < start + n; i++)
Console.Write(temp[i] + " ");
Console.WriteLine();
}
// Driver program
public static void Main ()
{
int []arr = {1, 3, 5, 7, 9};
int n = arr.Length;
int []temp = new int[2*n];
preprocess(arr, n, temp);
int k = 2;
leftRotate(arr, n, k, temp);
k = 3;
leftRotate(arr, n, k, temp);
k = 4;
leftRotate(arr, n, k, temp);
}
}
//This code is contributed by vt_m.
PHP
<?php
// PHP implementation of
// left rotation of an
// array K number of times
// Fills $temp with
// two copies of $arr
function preprocess(&$arr, $n,
&$temp)
{
// Store $arr elements
// at i and i + n
for ($i = 0; $i < $n; $i++)
$temp[$i] = $temp[$i + $n] = $arr[$i];
}
// Function to left rotate
// an array k times
function leftRotate(&$arr, $n,
$k, &$temp)
{
// Starting position of
// array after k rotations
// in temp[] will be k % n
$start = $k % $n;
// Print array after
// k rotations
for ($i = $start;
$i < $start + $n; $i++)
echo $temp[$i] . " ";
echo "\n";
}
// Driver Code
$arr = array(1, 3, 5, 7, 9);
$n = sizeof($arr);
$temp[2 * $n] = array();
preprocess($arr, $n, $temp);
$k = 2;
leftRotate($arr, $n, $k, $temp);
$k = 3;
leftRotate($arr, $n, $k, $temp);
$k = 4;
leftRotate($arr, $n, $k, $temp);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript implementation of left rotation of
// an array K number of times
// Fills temp with two copies of arr
function preprocess(arr , n , temp) {
// Store arr elements at i and i + n
for (i = 0; i < n; i++)
temp[i] = temp[i + n] = arr[i];
}
// Function to left rotate an array k time
function leftRotate(arr , n , k , temp) {
// Starting position of array after k
// rotations in temp will be k % n
var start = k % n;
// Print array after k rotations
for (i = start; i < start + n; i++)
document.write(temp[i] + " ");
document.write("<br/>");
}
// Driver program
var arr = [ 1, 3, 5, 7, 9 ];
var n = arr.length;
var temp = Array(2 * n).fill(0);
preprocess(arr, n, temp);
var k = 2;
leftRotate(arr, n, k, temp);
k = 3;
leftRotate(arr, n, k, temp);
k = 4;
leftRotate(arr, n, k, temp);
// This code contributed by gauravrajput1
</script>
Producción
5 7 9 1 3 7 9 1 3 5 9 1 3 5 7
Complejidad de tiempo: O(n)
Tenga en cuenta que la tarea de encontrar la dirección de inicio de la rotación requiere O(1) tiempo . Está imprimiendo los elementos que toman tiempo O(n).
Espacio Auxiliar: O(n)
Enfoque de espacio optimizado: el método anterior requiere espacio adicional. A continuación se muestra una solución optimizada para el espacio. Gracias a frenzy77 por sugerir este enfoque.
Implementación:
C++
// CPP implementation of left rotation of
// an array K number of times
#include<bits/stdc++.h>
using namespace std;
// Function to left rotate an array k times
void leftRotate(int arr[], int n, int k)
{
// Print array after k rotations
for (int i = k; i < k + n; i++)
cout << arr[i%n] << " ";
}
// Driver program
int main()
{
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
leftRotate(arr, n, k);
cout << endl;
k = 3;
leftRotate(arr, n, k);
cout << endl;
k = 4;
leftRotate(arr, n, k);
cout << endl;
return 0;
}
Java
// Java implementation of
// left rotation of an
// array K number of times
import java.io.*;
class GFG
{
// Function to left rotate
// an array k times
static void leftRotate(int arr[],
int n, int k)
{
// Print array after
// k rotations
for (int i = k; i < k + n; i++)
System.out.print(arr[i % n] + " ");
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {1, 3, 5, 7, 9};
int n = arr.length;
int k = 2;
leftRotate(arr, n, k);
System.out.println();
k = 3;
leftRotate(arr, n, k);
System.out.println();
k = 4;
leftRotate(arr, n, k);
System.out.println();
}
}
// This code is contributed by ajit
Python 3
# Python3 implementation of # left rotation of an array # K number of times # Function to left rotate # an array k times def leftRotate(arr, n, k): # Print array # after k rotations for i in range(k, k + n): print(str(arr[i % n]), end = " ") # Driver Code arr = [1, 3, 5, 7, 9] n = len(arr) k = 2; leftRotate(arr, n, k) print() k = 3; leftRotate(arr, n, k) print() k = 4 leftRotate(arr, n, k) print() # This code is contributed # by ChitraNayal
C#
// C# implementation of
// left rotation of an
// array K number of times
using System;
class GFG
{
// Function to left rotate
// an array k times
static void leftRotate(int []arr,
int n, int k)
{
// Print array after
// k rotations
for (int i = k; i < k + n; i++)
Console.Write(arr[i % n] + " ");
}
// Driver Code
static public void Main ()
{
int []arr = {1, 3, 5, 7, 9};
int n = arr.Length;
int k = 2;
leftRotate(arr, n, k);
Console.WriteLine();
k = 3;
leftRotate(arr, n, k);
Console.WriteLine();
k = 4;
leftRotate(arr, n, k);
Console.WriteLine();
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// PHP implementation of left rotation of
// an array K number of times
// Function to left rotate an array k times
function leftRotate($arr, $n, $k)
{
// Print array after k rotations
for ($i = $k; $i < $k + $n; $i++)
echo $arr[$i % $n] ," ";
}
// Driver program
$arr = array (1, 3, 5, 7, 9);
$n = sizeof($arr);
$k = 2;
leftRotate($arr, $n, $k);
echo "\n";
$k = 3;
leftRotate($arr, $n, $k);
echo "\n";
$k = 4;
leftRotate($arr, $n, $k);
echo "\n";
// This code is contributed by aj_36
?>
Javascript
<script>
// JavaScript implementation of
// left rotation of an
// array K number of times
// Function to left rotate
// an array k times
function leftRotate(arr, n, k)
{
// Print array after
// k rotations
for (let i = k; i < k + n; i++)
document.write(arr[i % n] + " ");
}
// Driver Code
let arr = [1, 3, 5, 7, 9];
n = arr.length;
k = 2;
leftRotate(arr, n, k);
document.write("<br>");
k = 3;
leftRotate(arr, n, k);
document.write("<br>");
k = 4;
leftRotate(arr, n, k);
document.write("<br>");
</script>
Producción
5 7 9 1 3 7 9 1 3 5 9 1 3 5 7
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de nuclode y Rohit Thapliyal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA