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

• {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.

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.

#include  using namespace std; void performQueries(int arr[], int N, vector> &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> queries; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}}; performQueries(arr, N, queries); return 0; }

Salin selepas log masuk

13 223

Salin selepas log masuk

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.

#include  using namespace std; void performQueries(int arr[], int N, vector> &queries) { // Queue to insert array elements deque 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> queries; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}}; performQueries(arr, N, queries); return 0; }

Salin selepas log masuk

13 223

Salin selepas log masuk

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!