按照给定的查询重新排列和更新数组元素

在这个问题中，我们将对数组元素执行给定的查询。查询包含数组元素的循环左旋转、右旋转和更新。

解决问题的逻辑部分是数组旋转。向左旋转数组的简单方法是将每个元素替换为下一个元素，将最后一个元素替换为第一个元素。

我们可以使用deque数据结构来高效地旋转数组。

问题陈述 - 我们给出了一个包含整数值的 arr[] 数组。此外，我们还给出了一个包含 K 个查询的 requests[] 数组。我们需要根据以下规则对 arr[] 数组元素执行 requests[] 中给出的每个查询。

• {0} - 对数组进行圆形左旋转。

• {1) - 对数组进行圆形右旋转。

• {2, p, q} - 用 q 更新第 p 个索引处的元素。

• {3, p} - 打印第 p 个索引中的元素。

示例

输入

arr[] = {8, 9, 13, 44, 76, 67, 21, 51}; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};

输出

13,223

解释- 让我们执行每个查询。

• {1} -> 将数组向右旋转后，数组变为 {51, 8, 9, 13, 44, 76, 67, 21}

• {0} -> 将更新后的数组向左旋转后，数组变为等于 {8, 9, 13, 44, 76, 67, 21, 51}。

• {2, 4, 50} -> 将索引 4 处的元素更新为 50 后，数组变为 {8, 9, 13, 44, 50, 67, 21, 51}

• {3, 2} -> 它打印第二个索引中的元素。

• {2, 2, 223}−> 将第二个索引处的元素更新为 223，数组变为 {8, 9, 223, 44, 50, 67, 21, 51}。 p>

• {3, 2} -> 它打印第二个索引中的元素。

输入

arr[] = {3, 2, 1}, {{3, 2}, {3, 0}}

输出

1,3

说明 - 它从第 2 个和第 0 个索引打印数组。

输入

arr[] = {76,20,51,78}, queries={{1},{1},{3, 1}}

输出

78

解释- 将数组向右旋转 2 次后，数组变为 [51, 78, 76, 20]。第一个索引处的元素是 78。

网龙b2b仿阿里巴巴电子商务平台

本系统经过多次升级改造，系统内核经过多次优化组合，已经具备相对比较方便快捷的个性化定制的特性，用户部署完毕以后，按照自己的运营要求，可实现快速定制会费管理，支持在线缴费和退费功能财富中心，管理会员的诚信度数据单客户多用户登录管理全部信息支持审批和排名不同的会员级别有不同的信息发布权限企业站单独生成，企业自主决定更新企业站信息留言、询价、报价统一管理，分系统查看分类信息参数化管理，支持多样分类信息，

下载

方法 1

在这种方法中，我们将遍历每个查询并根据给定的查询执行操作。我们将数组中的每个元素替换为下一个元素，以将其向左旋转，并将每个元素替换为前一个元素，以将其向右旋转。

算法

第 1 步- 开始遍历每个查询。

步骤 2− 如果查询[p][0]等于 0，请按照以下步骤操作。

步骤 2.1- 使用数组的第一个元素初始化“temp”变量。

步骤 2.2- 开始遍历数组，并将每个元素替换为下一个元素。

步骤 2.3- 将最后一个元素替换为“temp”值。

第 3 步− 如果查询[p][0] 等于 1，请按照以下步骤操作。

步骤 3.1- 将数组的最后一个元素存储在“temp”变量中。

步骤 3.2- 开始遍历数组，并将每个元素替换为前一个元素。

步骤 3.3- 使用“temp”值更新第一个元素。

第 4 步- 如果 requests[p][0] 为 2，则使用给定值更新给定索引处的数组元素。

第 5 步- 如果 requests[p][0] 为 3，则打印给定索引的数组值。

示例

#include 
using namespace std;

void performQueries(int arr[], int N, vector> &queries) {
    int len = queries.size();
    for (int p = 0; p < len; p++) {
        // For left shift
        if (queries[p][0] == 0) {
            //    left shift array
            int temp = arr[0];
            for (int p = 0; p < N - 1; p++){
                arr[p] = arr[p + 1];
            }
            arr[N - 1] = temp;
        }
        // For the right shift
        else if (queries[p][0] == 1) {
            // Right shift array
            int temp = arr[N - 1];
            for (int p = N - 1; p > 0; p--){
                arr[p] = arr[p - 1];
            }
            arr[0] = temp;
        }
        // For updating the value
        else if (queries[p][0] == 2) {
            arr[queries[p][1]] = queries[p][2];
        }
        // For printing the value
        else {
            cout << arr[queries[p][1]] << " ";
        }
    }
}
int main() {
    int arr[] = {8, 9, 13, 44, 76, 67, 21, 51};
    int N = sizeof(arr) / sizeof(arr[0]);
    vector> queries;
    queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};
    performQueries(arr, N, queries);
    return 0;
}

输出

13 223

时间复杂度 - O(N*K)，遍历查询并旋转数组。

空间复杂度 - O(1)，因为我们使用常量空间。

方法2

在这种方法中，我们将使用双端队列来存储数组元素。之后，要向左旋转数组，我们可以从队列中弹出前面的元素并将其推入队列的末尾。同样，我们可以将数组向正确的方向旋转。

算法

第 1 步- 定义双端队列并将所有数组元素推入队列。

步骤 2- 使用 for 循环遍历每个查询。

步骤 3- 要将数组向左旋转，请从队列开头删除第一个元素，并将其推到队列末尾。

第 4 步- 要沿正确方向旋转数组，请从队列末尾删除一个元素，并将该元素推入开头。

第 5 步- 根据给定的查询更新元素或打印元素值。

示例

#include 
using namespace std;

void performQueries(int arr[], int N, vector> &queries) {
    // Queue to insert array elements
    deque que;
    // Add elements to queue
    for (int p = 0; p < N; p++) {
        que.push_back(arr[p]);
    }
    // total queries
    int len = queries.size();
    for (int p = 0; p < len; p++) {
        // For left shift
        if (queries[p][0] == 0) {
            // Get the first element
            int temp = que[0];
            // Remove the first element
            que.pop_front();
            // Push element at the last
            que.push_back(temp);
        }
        // For the right shift
        else if (queries[p][0] == 1) {
            // Get the last element
            int temp = que[N - 1];
            // remove the last element
            que.pop_back();
            // Insert element at the start
            que.push_front(temp);
        }
        // For updating the value
        else if (queries[p][0] == 2) {
            que[queries[p][1]] = queries[p][2];
        }
        // For printing the value
        else {
            cout << que[queries[p][1]] << " ";
        }
    }
}
int main() {
    int arr[] = {8, 9, 13, 44, 76, 67, 21, 51};
    int N = sizeof(arr) / sizeof(arr[0]);
    vector> queries;
    queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};
    performQueries(arr, N, queries);
    return 0;
}

输出

13 223	

时间复杂度 - 将数组元素插入队列的 O(N+K)。

空间复杂度 - 将元素存储到双端队列中的 O(N)。

双端队列数据结构允许我们在 O(1) 时间内执行左右旋转操作。因此，它提高了执行给定查询的代码的效率。