資料結構
網路
關係資料庫管理系統(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 次檢視
