在这个问题中，我们将对数组元素执行给定的查询。查询包含数组元素的循环左旋转、右旋转和更新。
解决问题的逻辑部分是数组旋转。向左旋转数组的简单方法是将每个元素替换为下一个元素，将最后一个元素替换为第一个元素。
我们可以使用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) 时间内执行左右旋转操作。因此，它提高了执行给定查询的代码的效率。
