C++程序找出经过若干次旋转后给定索引处的元素

给定一个由N个整数组成的数组，我们可以进行[L..R]范围内的若干次右循环旋转。在进行这些旋转后，我们需要找到给定索引处的元素。

例如：

输入 ：arr[] : {1, 2, 3, 4, 5}
        ranges[] = { {0, 2}, {0, 3} }
        index : 1
输出 ：3
说明 ：第一次给定旋转 {0, 2}
                arr[] = {3, 1, 2, 4, 5}
              第二次旋转 {0, 3} 后
                arr[] = {4, 3, 1, 2, 5}
在所有旋转后，我们在给定的索引1处找到元素3。

方法：暴力法 暴力法的方法是将所有给定范围的数组都旋转一遍，最后返回修改后数组中给定索引处的元素。

方法：高效法 我们可以保存所有的旋转范围，并进行离线处理。

假设，我们的旋转范围是：[0..2]和[0..3]

我们从后往前遍历这些范围。

在范围[0..3]之后，索引0会有索引3的元素。

因此，我们可以将0更改为3，即如果索引=left，则索引将更改为right。

在范围[0..2]之后，索引3将保持不变。

因此，我们可以做出3种情况：

如果索引=left，则索引将更改为right。

如果索引不受范围约束，则旋转无效果。

如果索引位于范围内，则索引将具有索引-1处的元素。

下面是实现细节：

更好的解释：

10 20 30 40 50

索引：1

旋转范围：{0,2} {1,4} {0,3}

答案：在顺序{0,2} {1,4} {0,3}下，索引1将拥有30的所有3个旋转后。

我们对A执行{0,2}，现在我们有一个新的数组A1。

我们对A1执行{1,4}，现在我们有一个新的数组A2。

我们对A2执行{0,3}，现在我们有一个新的数组A3。

现在，我们正在A3中查找索引1处的值。

但是A3是在A2上进行{0,3}操作得到的。

因此，A3中的索引1是A2中的索引0。

但是A2是在A1上进行{1,4}操作得到的。

因此，A2中的索引0也是A1中的索引0，因为它不在范围{1,4}内。

但是A1是在A上进行{0,2}操作得到的。

因此，A1中的索引0是A中的索引2。

注意，我们按逆序处理旋转范围而不是按逆序旋转元素，只是从后往前处理索引。

因为如果我们实际上按逆序旋转，则可能会得到完全不同的答案，在旋转中顺序是重要的。

// CPP代码来旋转数组并回答索引查询
// 包括头文件
#include <bits/stdc++.h>
using namespace std;
 
// 计算给定索引处元素的函数
int findElement(int arr[], int ranges[][2],
               int rotations, int index)
{
    for (int i = rotations - 1; i >= 0; i--) {
 
        // 范围[left...right]
        int left = ranges[i][0];
        int right = ranges[i][1];
 
        // 旋转对该索引没有影响
        if (left <= index && right >= index) {
            if (index == left)
                index = right;
            else
                index--;
        }
    }
 
    // 返回新元素
    return arr[index];
}
 
// 主函数
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
 
    // 旋转次数
    int rotations = 2;
 
    // 根据0开始的索引设置范围
    int ranges[rotations][2] = { { 0, 2 }, { 0, 3 } };
 
    int index = 1;
 
    cout << findElement(arr, ranges, rotations, index);
 
    return 0;
 
}

输出:

时间复杂度: O(N)，其中N代表给定旋转次数。

辅助空间: O(1)，不需要额外的空间，因此是一个常数。