Imprimir array después de que se gire a la derecha K veces donde K puede ser grande o negativo

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N y un valor K ( -10^5<K<10^5 ) , la tarea es imprimir la array rotada K veces a la derecha.

Ejemplos:

Entrada: arr = {1, 3, 5, 7, 9}, K = 2
Salida: 7 9 1 3 5
Explicación: 
Array giratoria 1 vez a la derecha: 9, 1, 3, 5, 7
Array giratoria 2 vez a la derecha: 7 , 9, 1, 3, 5

Entrada: arr = {1, 2, 3, 4, 5}, K = -2
Salida: 3 4 5 1 2
Explicación: 
Array giratoria -1 vez a la derecha: 2, 3, 4, 5, 1
Array giratoria -2 veces derecha: 3, 4, 5, 1, 2

 

Enfoque ingenuo: el enfoque de fuerza bruta para resolver este problema es usar una array temporal para rotar la array K o -K veces.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver dividiéndolo en las siguientes partes:

  1. Redondee el valor de K en el rango [0, N), siguiendo los pasos a continuación:
    • Si K es negativo, primero cámbielo a positivo, encuentre el módulo con N y luego cámbielo nuevamente a negativo
    • Si K es positivo, solo encuentra el módulo con N
  2. Manejar el caso cuando K es negativo. Si K es negativo, significa que necesitamos rotar la array K veces a la izquierda o -K veces a la derecha.
  3. A continuación, podemos simplemente rotar el arreglo K veces invirtiendo los subarreglos. Se pueden seguir los siguientes pasos para resolver el problema:
    • Invierta todos los elementos de la array de 1 a N -1
    • Invierta los elementos de la array de 1 a K – 1
    • Invierta los elementos de la array de K a N -1

C++

// C++ implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to rotate the array
// to the right, K times
void RightRotate(vector<int>& nums, int K)
{
    int n = nums.size();
 
    // Case when K > N or K < -N
    K = K < 0 ? ((K * -1) % n) * -1 : K % n;
 
    // Case when K is negative
    K = K < 0 ? (n - (K * -1)) : K;
 
    // Reverse all the array elements
    reverse(nums.begin(), nums.end());
 
    // Reverse the first k elements
    reverse(nums.begin(), nums.begin() + K);
 
    // Reverse the elements from K
    // till the end of the array
    reverse(nums.begin() + K, nums.end());
}
 
// Driver code
int main()
{
 
    // Initialize the array
    vector<int> Array = { 1, 2, 3, 4, 5 };
 
    // Find the size of the array
    int N = Array.size();
 
    // Initialize K
    int K = -2;
 
    // Call the function and
    // print the answer
    RightRotate(Array, K);
 
    // Print the array after rotation
    for (int i = 0; i < N; i++) {
 
        cout << Array[i] << " ";
    }
 
    cout << endl;
    return 0;
}

Java

// Java implementation for the above approach
import java.util.*;
 
class GFG{
 
    // Initialize the array
   static int[] Array = { 1, 2, 3, 4, 5 };
    
   static void reverse( int start, int end) {
 
       // Temporary variable to store character
       int temp;
       while (start <= end)
       {
          
           // Swapping the first and last character
           temp = Array[start];
           Array[start] = Array[end];
           Array[end] = temp;
           start++;
           end--;
       }
   }
   
// Function to rotate the array
// to the right, K times
static void RightRotate( int K)
{
    int n = Array.length;
 
    // Case when K > N or K < -N
    K = K < 0 ? ((K * -1) % n) * -1 : K % n;
 
    // Case when K is negative
    K = K < 0 ? (n - (K * -1)) : K;
 
    // Reverse all the array elements
    reverse(0, n-1);
 
    // Reverse the first k elements
    reverse(0, n - K);
 
    // Reverse the elements from K
    // till the end of the array
    reverse( K, n-1);
}
 
// Driver code
public static void main(String[] args)
{
 
 
    // Find the size of the array
    int N = Array.length;
 
    // Initialize K
    int K = -2;
 
    // Call the function and
    // print the answer
    RightRotate(K);
 
    // Print the array after rotation
    for (int i = 0; i < N; i++) {
 
        System.out.print(Array[i]+ " ");
    }
 
    System.out.println();
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python code for the above approach
 
# Function to rotate the array
# to the right, K times
def RightRotate(nums, K) :
    n = len(nums)
 
    # Case when K > N or K < -N
    K = ((K * -1) % n) * -1 if K < 0 else K % n;
 
    # Case when K is negative
    K = (n - (K * -1)) if K < 0 else K;
 
    # Reverse all the array elements
    nums.reverse();
 
    # Reverse the first k elements
    p1 = nums[0:K]
    p1.reverse();
 
    # Reverse the elements from K
    # till the end of the array
    p2 = nums[K:]
    p2.reverse();
    arr = p1 + p2
 
    return arr;
 
# Driver code
 
# Initialize the array
Array = [1, 2, 3, 4, 5];
 
# Find the size of the array
N = len(Array)
 
# Initialize K
K = -2;
 
# Call the function and
# print the answer
Array = RightRotate(Array, K);
 
# Print the array after rotation
for i in Array:
    print(i, end=" ")
 
# This code is contributed by Saurabh jaiswal

C#

// C# implementation for the above approach
using System;
public class GFG {
 
  // Initialize the array
  static int[] Array = { 1, 2, 3, 4, 5 };
  static void reverse(int start, int end)
  {
 
    // Temporary variable to store character
    int temp;
    while (start <= end) {
 
      // Swapping the first and last character
      temp = Array[start];
      Array[start] = Array[end];
      Array[end] = temp;
      start++;
      end--;
    }
  }
 
  // Function to rotate the array
  // to the right, K times
  static void RightRotate(int K) {
    int n = Array.Length;
 
    // Case when K > N or K < -N
    K = K < 0 ? ((K * -1) % n) * -1 : K % n;
 
    // Case when K is negative
    K = K < 0 ? (n - (K * -1)) : K;
 
    // Reverse all the array elements
    reverse(0, n - 1);
 
    // Reverse the first k elements
    reverse(0, n - K);
 
    // Reverse the elements from K
    // till the end of the array
    reverse(K, n - 1);
  }
 
  // Driver code
  public static void Main(String[] args) {
 
    // Find the size of the array
    int N = Array.Length;
 
    // Initialize K
    int K = -2;
 
    // Call the function and
    // print the answer
    RightRotate(K);
 
    // Print the array after rotation
    for (int i = 0; i < N; i++) {
 
      Console.Write(Array[i] + " ");
    }
 
    Console.WriteLine();
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to rotate the array
       // to the right, K times
       function RightRotate(nums, K)
       {
           let n = nums.length;
 
           // Case when K > N or K < -N
           K = K < 0 ? ((K * -1) % n) * -1 : K % n;
 
           // Case when K is negative
           K = K < 0 ? (n - (K * -1)) : K;
 
           // Reverse all the array elements
           nums = nums.reverse();
 
           // Reverse the first k elements
           let p1 = nums.slice(0, K)
           p1 = p1.reverse();
 
           // Reverse the elements from K
           // till the end of the array
           let p2 = nums.slice(K)
           p2 = p2.reverse();
 
 
           let arr = p1.concat(p2);
 
           return arr;
       }
 
       // Driver code
 
 
       // Initialize the array
       let Array = [1, 2, 3, 4, 5];
 
       // Find the size of the array
       let N = Array.length;
 
       // Initialize K
       let K = -2;
 
       // Call the function and
       // print the answer
       Array = RightRotate(Array, K);
 
       // Print the array after rotation
       for (let i = 0; i < N; i++) {
 
           document.write(Array[i] + " ");
       }
       document.write('<br>')
 
      // This code is contributed by Potta Lokesh
   </script>
Producción

3 4 5 1 2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *