Susun semula dan kemas kini elemen tatasusunan mengikut pertanyaan yang diberikan

Dalam soalan ini, kami akan melaksanakan pertanyaan yang diberikan pada elemen tatasusunan. Pertanyaan mengandungi gelung putaran kiri, putaran kanan dan kemas kini elemen tatasusunan.

Bahagian logik untuk menyelesaikan masalah ialah putaran tatasusunan. Cara mudah untuk memutar tatasusunan ke kiri ialah menggantikan setiap elemen dengan elemen seterusnya dan elemen terakhir dengan elemen pertama.

Kita boleh menggunakan struktur data deque untuk memutar tatasusunan dengan cekap.

Pernyataan Masalah - Kami diberi tatasusunan arr[] yang mengandungi nilai integer. Selain itu, kami diberi tatasusunan permintaan[] yang mengandungi pertanyaan K. Kita perlu melaksanakan setiap pertanyaan yang diberikan dalam permintaan[] pada elemen tatasusunan arr[] mengikut peraturan berikut.

• {0} - Melakukan putaran kiri bulat pada tatasusunan.

• {1) - Lakukan putaran ke kanan bulatan pada tatasusunan.

• {2, p, q} - Mengemas kini elemen pada indeks p dengan q.

• {3, p} - Mencetak elemen pada indeks p.

Contoh

Masuk

arr[] = {8, 9, 13, 44, 76, 67, 21, 51}; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};

Output

13,223

Penjelasan- Mari kita laksanakan setiap pertanyaan.

• {1} -> Selepas memutar tatasusunan ke kanan, tatasusunan menjadi {51, 8, 9, 13, 44, 76, 67, 21}

• {0} -> Selepas memutar tatasusunan yang dikemas kini ke kiri, tatasusunan menjadi sama dengan {8, 9, 13, 44, 76, 67, 21, 51}.

• {2, 4, 50} -> Selepas mengemas kini elemen pada indeks 4 hingga 50, tatasusunan menjadi {8, 9, 13, 44, 50, 67, 21, 51}#🎜 🎜 #

• {3, 2} -> Ia mencetak elemen dalam indeks kedua.

• {2, 2, 223}−> Kemas kini elemen pada indeks kedua kepada 223 dan tatasusunan menjadi {8, 9, 223, 44, 50, 67, 21, 51}.

  p>

• {3, 2} -> Ia mencetak elemen dalam indeks kedua.

Masuk

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

Output

1,3

Penerangan - Ia mencetak tatasusunan daripada indeks ke-2 dan ke-0.

Masuk

arr[] = {76,20,51,78}, queries={{1},{1},{3, 1}}

Output

78

Penjelasan- Selepas memutar tatasusunan ke kanan 2 kali, tatasusunan menjadi [51, 78, 76, 20]. Elemen pada indeks pertama ialah 78.

Kaedah 1

Dalam kaedah ini, kami akan mengulangi setiap pertanyaan dan melaksanakan operasi berdasarkan pertanyaan yang diberikan. Kami menggantikan setiap elemen dalam tatasusunan dengan elemen seterusnya untuk memutarkannya ke kiri, dan setiap elemen dengan elemen sebelumnya untuk memutarkannya ke kanan.

Algoritma

Langkah 1 - Mulakan gelung melalui setiap pertanyaan.

Langkah 2− Jika pertanyaan[p][0] bersamaan dengan 0, sila ikut langkah di bawah.

Langkah 2.1- Mulakan pembolehubah "temp" menggunakan elemen pertama tatasusunan.

Langkah 2.2- Mula melintasi tatasusunan dan gantikan setiap elemen dengan elemen seterusnya.

Langkah 2.3- Gantikan elemen terakhir dengan nilai "temp".

Langkah 3− Jika pertanyaan[p][0] bersamaan dengan 1, ikut langkah ini.

Langkah 3.1- Simpan elemen terakhir tatasusunan dalam pembolehubah "temp".

Langkah 3.2- Mula melintasi tatasusunan dan gantikan setiap elemen dengan elemen sebelumnya.

Langkah 3.3- Kemas kini elemen pertama dengan nilai "temp".

Langkah 4- Jika permintaan[p][0] ialah 2, kemas kini elemen tatasusunan pada indeks yang diberikan dengan nilai yang diberikan.

Langkah 5- Jika permintaan[p][0] ialah 3, cetak nilai tatasusunan pada indeks yang diberikan.

Contoh

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

Output

13 223

Kerumitan masa - O(N*K), lalui pertanyaan dan putar tatasusunan.

Kerumitan ruang - O(1) kerana kami menggunakan ruang malar.

Kaedah 2

Dalam kaedah ini, kita akan menggunakan deque untuk menyimpan elemen tatasusunan. Selepas itu, untuk memutar tatasusunan ke kiri, kita boleh meletuskan elemen sebelumnya dari baris gilir dan menolaknya ke penghujung baris gilir. Begitu juga, kita boleh memutarkan tatasusunan ke arah yang betul.

Algoritma

Langkah 1 - Tentukan deque dan tolak semua elemen tatasusunan ke dalam baris gilir.

Langkah 2- Gunakan gelung for untuk mengulangi setiap pertanyaan.

Langkah 3- Untuk memutar tatasusunan ke kiri, alih keluar elemen pertama dari permulaan baris gilir dan tolaknya ke penghujung baris gilir.

Langkah 4 - Untuk memutar tatasusunan ke arah yang betul, alih keluar elemen dari penghujung baris gilir dan tolak elemen itu ke permulaan.

Langkah 5 - Kemas kini elemen atau cetak nilai elemen berdasarkan pertanyaan yang diberikan.

Contoh

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

Output

13 223	

Kerumitan masa - O(N+K) untuk memasukkan elemen tatasusunan ke dalam baris gilir.

Kerumitan Ruang - O(N) untuk menyimpan elemen ke dalam deque.

Struktur data deque membolehkan kami melakukan operasi putaran kiri dan kanan dalam masa O(1). Oleh itu, ia meningkatkan kecekapan kod yang melaksanakan pertanyaan yang diberikan.

Atas ialah kandungan terperinci Susun semula dan kemas kini elemen tatasusunan mengikut pertanyaan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!