按照給定的查詢重新排列和更新數組元素-C++-PHP中文網

方法2

演算法

範例

輸出

首頁

後端開發

C++

按照給定的查詢重新排列和更新數組元素

Sep 14, 2023 pm 04:29 PM

陣列更新重新排列

按照給定的查詢重新排列和更新數組元素

在這個問題中，我們將對陣列元素執行給定的查詢。查詢包含陣列元素的循環左旋轉、右旋轉和更新。

解決問題的邏輯部分是陣列旋轉。向左旋轉數組的簡單方法是將每個元素替換為下一個元素，將最後一個元素替換為第一個元素。

我們可以使用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}。
{3, 2} -> 它列印第二個索引中的元素。

輸入

arr[] = {3, 2, 1}, {{3, 2}, {3, 0}}

登入後複製

輸出

1,3

登入後複製

說明 - 它從第 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;
}

登入後複製

輸出

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;
}

登入後複製