极客笔记C++ 重新排列和更新数组元素
在这个问题中，我们将对数组元素执行给定的查询操作。这些查询包括循环左旋、右旋和数组元素的更新。
解决问题的逻辑部分是数组旋转。将数组向左方向旋转的简单方法是用下一个元素替换每个元素，并用第一个元素替换最后一个元素。
我们可以使用双端队列数据结构高效地旋转数组。
问题陈述： 给定一个包含整数值的arr[]数组。同时，给定一个包含K个查询的queries[]数组。我们需要根据以下规则对arr[]数组的每个查询进行操作。
- {0} – 对数组进行循环左旋。
-
{1} – 对数组进行循环右旋。
-
{2, p, q} – 将第p个索引处的元素更新为q。
-
{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, 2, 223} -> 将第2个索引位置的元素更新为223，数组变为{8, 9, 223, 44, 50, 67, 21, 51}。
-
{3, 2} -> 打印第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 − 如果queries[p][0]等于0，则按照以下步骤进行操作。
步骤2.1 − 将’temp’变量初始化为数组的第一个元素。
步骤2.2 − 开始遍历数组，并将每个元素替换为下一个元素。
步骤2.3 − 将最后一个元素替换为’temp’的值。
步骤3 − 如果queries[p][0]等于1，则按照以下步骤进行操作。
步骤3.1 − 将数组的最后一个元素存储在’temp’变量中。
步骤3.2 − 开始遍历数组，并将每个元素替换为前一个元素。
步骤3.3 − 将第一个元素更新为’temp’的值。
步骤4 − 如果queries[p][0]为2，则使用给定的值更新给定索引处的数组元素。
步骤5 − 如果queries[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
在这种方法中，我们将使用deque来存储数组的元素。之后，为了向左旋转数组，我们可以从队列的前面弹出元素，并将其推到队列的末尾。同样地，我们可以向右旋转数组。
步骤
第1步 - 定义deque并将所有数组元素推入队列。
第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)的时间内执行右旋和左旋操作。因此，它提高了执行给定查询的代码的效率。