在这个问题中，我们将对数组元素执行给定的查询。查询包含数组元素的循环左旋转、右旋转和更新。
解决问题的逻辑部分是数组旋转。向左旋转数组的简单方法是将每个元素替换为下一个元素，将最后一个元素替换为第一个元素。
我们可以使用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 using namespace std;void performQueries(int arr[], int N, vector<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 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> 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<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<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) 时间内执行左右旋转操作。因此，它提高了执行给定查询的代码的效率。
以上就是按照给定的查询重新排列和更新数组元素的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445168.html
微信扫一扫 
支付宝扫一扫 
