Se da una array que consta de N enteros. Hay varias rotaciones circulares derechas de rango [L..R] que realizamos. Después de realizar estas rotaciones, necesitamos encontrar un elemento en un índice dado.
Ejemplos:
Input : arr[] : {1, 2, 3, 4, 5}
ranges[] = { {0, 2}, {0, 3} }
index : 1
Output : 3
Explanation : After first given rotation {0, 2}
arr[] = {3, 1, 2, 4, 5}
After second rotation {0, 3}
arr[] = {4, 3, 1, 2, 5}
After all rotations we have element 3 at given
index 1.
Método: fuerza bruta El enfoque de fuerza bruta consiste en rotar la array para todos los rangos dados y, finalmente, devolver el elemento en el índice dado en la array modificada.
Método: Eficiente Podemos hacer el procesamiento fuera de línea después de guardar todos los rangos.
Supongamos que nuestros rangos de rotación son: [0..2] y [0..3]
Corremos a través de estos rangos desde el reverso.
Después del rango [0..3], el índice 0 tendrá el elemento que estaba en el índice 3.
Entonces, podemos cambiar 0 a 3, es decir, si el índice = izquierda, el índice se cambiará a la derecha.
Después del rango [0..2], el índice 3 no se verá afectado.
Entonces, podemos hacer 3 casos:
si índice = izquierda, el índice se cambiará a la derecha.
Si el índice no está acotado por el rango, no hay efecto de rotación.
Si el índice está dentro de los límites, el índice tendrá el elemento en índice-1.
A continuación se muestra la implementación:
Para una mejor explicación: –
10 20 30 40 50
Índice: 1
Rotaciones: {0,2} {1,4} {0,3}
Respuesta: el índice 1 tendrá 30 después de las 3 rotaciones en el orden {0,2} {1,4} {0,3}.
Realizamos {0,2} en A y ahora tenemos una nueva array A1.
Realizamos {1,4} en A1 y ahora tenemos una nueva array A2.
Realizamos {0,3} en A2 y ahora tenemos una nueva array A3.
Ahora estamos buscando el valor en el índice 1 en A3.
Pero A3 se hace {0,3} en A2.
Entonces, el índice 1 en A3 es el índice 0 en A2.
Pero A2 se hace {1,4} en A1.
Entonces, el índice 0 en A2 también es el índice 0 en A1, ya que no se encuentra en el rango {1,4}.
Pero A1 se hace {0,2} en A.
Entonces, el índice 0 en A1 es el índice 2 en A.
Al observarlo, vamos profundizando en las rotaciones anteriores a partir de la última rotación.
{0,3}
|
{1,4}
|
{0,2}
Esta es la razón por la que estamos procesando las rotaciones en orden inverso.
Tenga en cuenta que no estamos rotando los elementos en el orden inverso, solo procesando el índice desde el reverso.
Porque si realmente rotamos en orden inverso, podríamos obtener una respuesta completamente diferente, ya que en el caso de las rotaciones, el orden importa.
C++
// CPP code to rotate an array
// and answer the index query
#include <bits/stdc++.h>
using namespace std;
// Function to compute the element at
// given index
int findElement(int arr[], int ranges[][2],
int rotations, int index)
{
for (int i = rotations - 1; i >= 0; i--) {
// Range[left...right]
int left = ranges[i][0];
int right = ranges[i][1];
// Rotation will not have any effect
if (left <= index && right >= index) {
if (index == left)
index = right;
else
index--;
}
}
// Returning new element
return arr[index];
}
// Driver
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
// No. of rotations
int rotations = 2;
// Ranges according to 0-based indexing
int ranges[rotations][2] = { { 0, 2 }, { 0, 3 } };
int index = 1;
cout << findElement(arr, ranges, rotations, index);
return 0;
}
C
// C code to rotate an array
// and answer the index query
#include <stdio.h>
// Function to compute the element at
// given index
int findElement(int arr[], int ranges[][2], int rotations,
int index)
{
for (int i = rotations - 1; i >= 0; i--) {
// Range[left...right]
int left = ranges[i][0];
int right = ranges[i][1];
// Rotation will not have any effect
if (left <= index && right >= index) {
if (index == left)
index = right;
else
index--;
}
}
// Returning new element
return arr[index];
}
// Driver
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
// No. of rotations
int rotations = 2;
// Ranges according to 0-based indexing
int ranges[2][2] = { { 0, 2 }, { 0, 3 } };
int index = 1;
printf("%d",
findElement(arr, ranges, rotations, index));
return 0;
}
// This code is contributed by Deepthi
Java
// Java code to rotate an array
// and answer the index query
import java.util.*;
class GFG
{
// Function to compute the element at
// given index
static int findElement(int[] arr, int[][] ranges,
int rotations, int index)
{
for (int i = rotations - 1; i >= 0; i--) {
// Range[left...right]
int left = ranges[i][0];
int right = ranges[i][1];
// Rotation will not have any effect
if (left <= index && right >= index) {
if (index == left)
index = right;
else
index--;
}
}
// Returning new element
return arr[index];
}
// Driver
public static void main (String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
// No. of rotations
int rotations = 2;
// Ranges according to 0-based indexing
int[][] ranges = { { 0, 2 }, { 0, 3 } };
int index = 1;
System.out.println(findElement(arr, ranges,
rotations, index));
}
}
/* This code is contributed by Mr. Somesh Awasthi */
Python3
# Python 3 code to rotate an array # and answer the index query # Function to compute the element # at given index def findElement(arr, ranges, rotations, index) : for i in range(rotations - 1, -1, -1 ) : # Range[left...right] left = ranges[i][0] right = ranges[i][1] # Rotation will not have # any effect if (left <= index and right >= index) : if (index == left) : index = right else : index = index - 1 # Returning new element return arr[index] # Driver Code arr = [ 1, 2, 3, 4, 5 ] # No. of rotations rotations = 2 # Ranges according to # 0-based indexing ranges = [ [ 0, 2 ], [ 0, 3 ] ] index = 1 print(findElement(arr, ranges, rotations, index)) # This code is contributed by Nikita Tiwari.
C#
// C# code to rotate an array
// and answer the index query
using System;
class GFG
{
// Function to compute the
// element at given index
static int findElement(int []arr, int [,]ranges,
int rotations, int index)
{
for (int i = rotations - 1; i >= 0; i--)
{
// Range[left...right]
int left = ranges[i, 0];
int right = ranges[i, 1];
// Rotation will not
// have any effect
if (left <= index &&
right >= index)
{
if (index == left)
index = right;
else
index--;
}
}
// Returning new element
return arr[index];
}
// Driver Code
public static void Main ()
{
int []arr = { 1, 2, 3, 4, 5 };
// No. of rotations
int rotations = 2;
// Ranges according
// to 0-based indexing
int [,]ranges = { { 0, 2 },
{ 0, 3 } };
int index = 1;
Console.Write(findElement(arr, ranges,
rotations,
index));
}
}
// This code is contributed
// by nitin mittal.
PHP
<?php
// PHP code to rotate an array
// and answer the index query
// Function to compute the
// element at given index
function findElement($arr, $ranges,
$rotations, $index)
{
for ($i = $rotations - 1;
$i >= 0; $i--)
{
// Range[left...right]
$left = $ranges[$i][0];
$right = $ranges[$i][1];
// Rotation will not
// have any effect
if ($left <= $index &&
$right >= $index)
{
if ($index == $left)
$index = $right;
else
$index--;
}
}
// Returning new element
return $arr[$index];
}
// Driver Code
$arr = array(1, 2, 3, 4, 5);
// No. of rotations
$rotations = 2;
// Ranges according
// to 0-based indexing
$ranges = array(array(0, 2),
array(0, 3));
$index = 1;
echo findElement($arr, $ranges,
$rotations, $index);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript code to rotate an array
// and answer the index query
// Function to compute the element at
// given index
let findElement = (arr, ranges,rotations,index)=>{
for (let i = rotations - 1; i >= 0; i--) {
// Range[left...right]
let left = ranges[i][0];
let right = ranges[i][1];
// Rotation will not have any effect
if (left <= index && right >= index) {
if (index == left)
index = right;
else
index--;
}
}
// Returning new element
return arr[index];
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5 ];
// No. of rotations
let rotations = 2;
// Ranges according to 0-based indexing
let ranges = [ [ 0, 2 ], [ 0, 3] ];
let index = 1;
document.write(findElement(arr, ranges, rotations, index));
</script>
Producción :
3
Complejidad del tiempo: O(R), R es el número de rotaciones
Espacio Auxiliar: O(1),
Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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