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

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

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

我们可以使用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。

方法 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 <bits/stdc++.h>
using namespace std;

void performQueries(int arr[], int N, vector<vector<int>> &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<vector<int>> 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 <bits/stdc++.h>
using namespace std;

void performQueries(int arr[], int N, vector<vector<int>> &queries) {
    // Queue to insert array elements
    deque<int> 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<vector<int>> 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) 时间内执行左右旋转操作。因此，它提高了执行给定查询的代码的效率。

以上是按照给定的查询重新排列和更新数组元素的详细内容。更多信息请关注PHP中文网其他相关文章！