数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学根据给定查询重新排列和更新数组元素
在这个问题中，我们将对数组元素执行给定的查询。查询包含数组元素的循环左移、右移和更新。
解决问题的逻辑部分是数组旋转。向左旋转数组的简单方法是用下一个元素替换每个元素，用第一个元素替换最后一个元素。
我们可以使用双端队列数据结构来有效地旋转数组。
问题陈述−我们有一个包含整数值的arr[]数组。此外，我们还有一个包含K个查询的queries[]数组。我们需要根据以下规则对arr[]数组元素执行queries[]中给出的每个查询。
{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} −> 用50更新第4个索引处的元素后，数组变为 {8, 9, 13, 44, 50, 67, 21, 51}。
{3, 2} −> 它打印第2个索引处的元素。
{2, 2, 223}−> 它用223更新第2个索引处的元素，数组变为 {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
在这种方法中，我们将使用双端队列来存储数组元素。之后，要向左旋转数组，我们可以从队列中弹出第一个元素并将其推送到队列的末尾。类似地，我们可以向右旋转数组。
算法
步骤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)时间内执行向右和向左旋转操作。因此，它提高了执行给定查询的代码效率。
177 次查看
