Ordnen Sie Array-Elemente entsprechend einer bestimmten Abfrage neu an und aktualisieren Sie sie

In dieser Frage führen wir die angegebene Abfrage für die Array-Elemente aus. Die Abfrage enthält eine Schleife aus Linksdrehung, Rechtsdrehung und Aktualisierung von Array-Elementen.

Der logische Teil zur Lösung des Problems ist die Array-Rotation. Eine einfache Möglichkeit, ein Array nach links zu drehen, besteht darin, jedes Element durch das nächste Element und das letzte Element durch das erste Element zu ersetzen.

Wir können die Deque-Datenstruktur verwenden, um das Array effizient zu drehen.

Problemstellung - Wir erhalten ein arr[]-Array mit ganzzahligen Werten. Zusätzlich erhalten wir ein request[]-Array mit K Abfragen. Wir müssen jede in „requests[]“ angegebene Abfrage für arr[]-Array-Elemente gemäß den folgenden Regeln ausführen.

• {0} – führt eine kreisförmige Drehung nach links auf dem Array durch.

• {1) – führt eine kreisförmige Rechtsdrehung des Arrays durch.

• {2, p, q} – Aktualisiert das Element am Index p mit q.

• {3, p} – druckt das Element am Index p.

Beispiel

Eintreten

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

Ausgabe

13,223

Erläuterung- Lassen Sie uns jede Abfrage ausführen.

• {1} -> Nach dem Drehen des Arrays nach rechts wird das Array zu {51, 8, 9, 13, 44, 76, 67, 21}

• {0} -> Nach dem Drehen des aktualisierten Arrays nach links wird das Array gleich {8, 9, 13, 44, 76, 67, 21, 51}.

• {2, 4, 50} -> Nach dem Aktualisieren des Elements am Index 4 auf 50 wird das Array zu {8, 9, 13, 44, 50, 67, 21, 51}

• {3, 2} -> Es gibt das Element im zweiten Index aus.

• {2, 2, 223}−> Aktualisieren Sie das Element am zweiten Index auf 223 und das Array wird zu {8, 9, 223, 44, 50, 67, 21, 51}. p>

• {3, 2} -> Es gibt das Element im zweiten Index aus.

Eintreten

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

Ausgabe

1,3

Beschreibung – Es wird das Array ab dem 2. und 0. Index gedruckt.

Eintreten

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

Ausgabe

78

Erklärung- Nachdem das Array zweimal nach rechts gedreht wurde, wird das Array zu [51, 78, 76, 20]. Das Element am ersten Index ist 78.

Methode 1

Bei dieser Methode durchlaufen wir jede Abfrage und führen Operationen basierend auf der angegebenen Abfrage aus. Wir ersetzen jedes Element im Array durch das nächste Element, um es nach links zu drehen, und jedes Element durch das vorherige Element, um es nach rechts zu drehen.

Algorithmus

Schritt 1 – Beginnen Sie mit dem Durchlaufen jeder Abfrage.

Schritt 2− Wenn query[p][0] gleich 0 ist, führen Sie bitte die folgenden Schritte aus.

Schritt 2.1- Initialisieren Sie die Variable „temp“ mit dem ersten Element des Arrays.

Schritt 2.2 – Beginnen Sie mit dem Durchlaufen des Arrays und ersetzen Sie jedes Element durch das nächste Element.

Schritt 2.3- Ersetzen Sie das letzte Element durch den „temp“-Wert.

Schritt 3− Wenn query[p][0] gleich 1 ist, befolgen Sie diese Schritte.

Schritt 3.1- Speichern Sie das letzte Element des Arrays in der Variablen „temp“.

Schritt 3.2 – Beginnen Sie mit dem Durchlaufen des Arrays und ersetzen Sie jedes Element durch das vorherige Element.

Schritt 3.3 – Aktualisieren Sie das erste Element mit dem „temp“-Wert.

Schritt 4 – Wenn „requests[p][0]“ 2 ist, aktualisieren Sie das Array-Element am angegebenen Index mit dem angegebenen Wert.

Schritt 5 – Wenn request[p][0] 3 ist, geben Sie den Array-Wert am angegebenen Index aus.

Beispiel

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

Ausgabe

13 223

Zeitkomplexität – O(N*K), Abfrage durchlaufen und Array drehen.

Raumkomplexität – O(1), weil wir konstanten Raum verwenden.

Methode 2

In dieser Methode verwenden wir deque zum Speichern von Array-Elementen. Um das Array anschließend nach links zu drehen, können wir das vorherige Element aus der Warteschlange entfernen und an das Ende der Warteschlange schieben. Ebenso können wir das Array in die richtige Richtung drehen.

Algorithmus

Schritt 1 – Definieren Sie die Deque und verschieben Sie alle Array-Elemente in die Warteschlange.

Schritt 2 – Verwenden Sie eine for-Schleife, um jede Abfrage zu durchlaufen.

Schritt 3 – Um das Array nach links zu drehen, entfernen Sie das erste Element vom Anfang der Warteschlange und schieben Sie es an das Ende der Warteschlange.

Schritt 4 – Um das Array in die richtige Richtung zu drehen, entfernen Sie ein Element vom Ende der Warteschlange und schieben Sie dieses Element an den Anfang.

Schritt 5 – Aktualisieren Sie das Element oder drucken Sie den Elementwert basierend auf der angegebenen Abfrage.

Beispiel

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

Ausgabe

13 223	

Zeitliche Komplexität – O(N+K) zum Einfügen von Array-Elementen in die Warteschlange.

Space Complexity – O(N) zum Speichern von Elementen in einer Deque.

Die Deque-Datenstruktur ermöglicht es uns, Links- und Rechtsrotationsoperationen in O(1)-Zeit durchzuführen. Dadurch wird die Effizienz des Codes verbessert, der eine bestimmte Abfrage ausführt.

Das obige ist der detaillierte Inhalt vonOrdnen Sie Array-Elemente entsprechend einer bestimmten Abfrage neu an und aktualisieren Sie sie. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!