算法题：旋转几次后，在给定索引处查找元素

本文概述

• 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 = 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
?>

输出：

3

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。