Dada una array arr[] de enteros y otro entero D , la tarea es realizar D rotaciones circulares en la array e imprimir la array modificada. Ejemplos:
Entrada: Arr[] = {1, 2, 3, 4, 5, 6}, D = 2 Salida: 5 6 1 2 3 4 Entrada: Arr[] = {1, 2, 3}, D = 2 Salida: 2 3 1
Enfoque: Usando Deque en C++, se puede realizar una rotación eliminando el último elemento del deque e insertándolo al comienzo del mismo deque. De manera similar, se pueden realizar todas las rotaciones requeridas y luego imprimir el contenido de la deque modificada para obtener la array rotada requerida. Si el número de rotaciones es mayor que el tamaño del deque, simplemente tome el mod con N , Entonces, D = D%N . Donde D es el número de rotaciones y N es el tamaño del deque. A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to circular rotate // the array by d elements void rotate(deque<int> deq, int d, int n) { // Push first d elements // from last to the beginning for (int i = 0; i < d; i++) { int val = deq.back(); deq.pop_back(); deq.push_front(val); } // Print the rotated array for (int i = 0; i < n; i++) { cout << deq[i] << " "; } cout << endl; } // Driver code int main() { deque<int> v = { 1, 2, 3, 4, 5, 6, 7 }; int n = v.size(); int d = 5; rotate(v, d % n, n); }
3 4 5 6 7 1 2
Complejidad temporal: O(n)
Espacio auxiliar: O(n)