算法题（旋转几次后，在给定索引处查找元素） _数据结构

本文概述

C ++
Java
Python3
C#
的PHP

给出了由N个整数组成的数组。有几个右圆旋转我们执行的范围[L..R]。完成这些旋转之后, 我们需要在给定索引处找到元素。
例子：

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.

方法：蛮力蛮力方法是旋转阵列对于所有给定范围, 最后返回修改后数组中给定索引处的元素。
方法：高效-保存所有范围后, 我们可以进行离线处理。
假设我们的旋转范围是：[0..2]和[0..3]
我们从反向开始遍历这些范围。
在范围[0..3]之后, 索引0将具有在索引3上的元素。
因此, 我们可以将0更改为3, 即, 如果index = left, 则index将更改为right。
在范围[0..2]之后, 索引3将保持不受影响。
因此, 我们可以提出3种情况：
1. 如果index = left, 则索引将更改为right。
2. 如果索引不受范围限制, 则没有旋转效果。
3. 如果index是有界的, 则index将在index-1处具有元素。
下面是实现：
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; }

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 = 1print (findElement(arr, ranges, rotations, index))# This code is contributed by Nikita Tiwari.

// 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 ?>

输出：