Réorganiser et mettre à jour les éléments du tableau en fonction d'une requête donnée

Dans cette question, nous exécuterons la requête donnée sur les éléments du tableau. La requête contient une boucle de rotation à gauche, de rotation à droite et de mise à jour des éléments du tableau.

La partie logique de la résolution du problème est la rotation du tableau. Un moyen simple de faire pivoter un tableau vers la gauche consiste à remplacer chaque élément par l’élément suivant et le dernier élément par le premier élément.

Nous pouvons utiliser la structure de données deque pour faire pivoter le tableau efficacement.

Énoncé du problème - On nous donne un tableau arr[] contenant des valeurs entières. De plus, nous recevons un tableau requêtes[] contenant K requêtes. Nous devons exécuter chaque requête donnée dans request[] sur les éléments du tableau arr[] selon les règles suivantes.

• {0} : effectue une rotation circulaire vers la gauche sur le tableau.

• {1) - effectue une rotation circulaire à droite du tableau.

• {2, p, q} - Met à jour l'élément à l'index p avec q.

• {3, p} - imprime l'élément à l'index p.

Exemple

Entrez

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

Sortie

13,223

Explication- Exécutons chaque requête.

• {1} -> Après avoir fait pivoter le tableau vers la droite, le tableau devient {51, 8, 9, 13, 44, 76, 67, 21}

• {0} -> Après avoir fait pivoter le tableau mis à jour vers la gauche, le tableau devient égal à {8, 9, 13, 44, 76, 67, 21, 51}.

• {2, 4, 50} -> Après avoir mis à jour l'élément à l'index 4 à 50, le tableau devient {8, 9, 13, 44, 50, 67, 21, 51}

• {3, 2} -> Il imprime l'élément dans le deuxième index.

• {2, 2, 223}−> Mettez à jour l'élément au deuxième index à 223, et le tableau devient {8, 9, 223, 44, 50, 67, 21, 51}. p>

• {3, 2} -> Il imprime l'élément dans le deuxième index.

Entrez

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

Sortie

1,3

Description - Il imprime le tableau à partir du 2ème et du 0ème index.

Entrez

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

Sortie

78

Explication- Après avoir fait pivoter le tableau vers la droite 2 fois, le tableau devient [51, 78, 76, 20]. L'élément au premier index est 78.

Méthode 1

Dans cette méthode, nous allons parcourir chaque requête et effectuer des opérations basées sur la requête donnée. Nous remplaçons chaque élément du tableau par l'élément suivant pour le faire pivoter vers la gauche, et chaque élément par l'élément précédent pour le faire pivoter vers la droite.

Algorithme

Étape 1- Commencez à parcourir chaque requête.

Étape 2− Si query[p][0] est égal à 0, veuillez suivre les étapes ci-dessous.

Étape 2.1- Initialisez la variable "temp" en utilisant le premier élément du tableau.

Étape 2.2- Commencez à parcourir le tableau et remplacez chaque élément par l'élément suivant.

Étape 2.3- Remplacez le dernier élément par la valeur "temp".

Étape 3− Si query[p][0] est égal à 1, suivez ces étapes.

Étape 3.1- Stockez le dernier élément du tableau dans la variable "temp".

Étape 3.2- Commencez à parcourir le tableau et remplacez chaque élément par l'élément précédent.

Étape 3.3- Mettez à jour le premier élément avec la valeur "temp".

Étape 4- Si requêtes[p][0] est 2, mettez à jour l'élément du tableau à l'index donné avec la valeur donnée.

Étape 5- Si requêtes[p][0] est 3, imprimez la valeur du tableau à l'index donné.

Exemple

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

Sortie

13 223

Complexité temporelle - O(N*K), parcourez la requête et faites pivoter le tableau.

Complexité spatiale - O(1) car nous utilisons un espace constant.

Méthode 2

Dans cette méthode, nous utiliserons deque pour stocker les éléments du tableau. Ensuite, pour faire pivoter le tableau vers la gauche, nous pouvons retirer l'élément précédent de la file d'attente et le pousser jusqu'à la fin de la file d'attente. De même, nous pouvons faire pivoter le tableau dans la bonne direction.

Algorithme

Étape 1- Définissez le deque et placez tous les éléments du tableau dans la file d'attente.

Étape 2- Utilisez une boucle for pour parcourir chaque requête.

Étape 3- Pour faire pivoter le tableau vers la gauche, supprimez le premier élément du début de la file d'attente et poussez-le jusqu'à la fin de la file d'attente.

Étape 4- Pour faire pivoter le tableau dans le bon sens, supprimez un élément de la fin de la file d'attente et poussez cet élément vers le début.

Étape 5- Mettez à jour l'élément ou imprimez la valeur de l'élément en fonction de la requête donnée.

Exemple

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

Sortie

13 223	

Complexité temporelle - O(N+K) pour insérer des éléments du tableau dans la file d'attente.

Space Complexity - O(N) pour stocker des éléments dans un deque.

La structure de données deque nous permet d'effectuer des opérations de rotation gauche et droite en temps O(1). Par conséquent, cela améliore l’efficacité du code qui exécute une requête donnée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!