在這個問題中，我們將對陣列元素執行給定的查詢。查詢包含陣列元素的循環左旋轉、右旋轉和更新。
解決問題的邏輯部分是陣列旋轉。向左旋轉數組的簡單方法是將每個元素替換為下一個元素，將最後一個元素替換為第一個元素。
我們可以使用deque資料結構來有效率地旋轉陣列。
問題陳述 - 我們給了一個包含整數值的 arr[] 陣列。此外，我們也給了一個包含 K 個查詢的 requests[] 陣列。我們需要根據以下規則對 arr[] 數組元素執行 requests[] 中給出的每個查詢。
範例
輸入
arr[] = {8, 9, 13, 44, 76, 67, 21, 51}; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};
登入後複製
輸出
解釋- 讓我們執行每個查詢。
{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}。
{3, 2} -> 它列印第二個索引中的元素。
輸入
arr[] = {3, 2, 1}, {{3, 2}, {3, 0}}
登入後複製
輸出
說明 - 它從第 2 和第 0 個索引列印陣列。
輸入
arr[] = {76,20,51,78}, queries={{1},{1},{3, 1}}
登入後複製
輸出
解釋- 將陣列向右旋轉 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;
}
登入後複製
輸出
時間複雜度 - 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;
}
登入後複製
輸出
時間複雜度 - 將陣列元素插入佇列的 O(N K)。
空間複雜度 - 將元素儲存到雙端佇列中的 O(N)。
雙端佇列資料結構允許我們在 O(1) 時間內執行左右旋轉操作。因此，它提高了執行給定查詢的程式碼的效率。
以上是按照給定的查詢重新排列和更新數組元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！
