Reduzieren Sie ein Array durch die angegebene Operation auf höchstens ein Element

In diesem Problem reduzieren wir die Array-Größe auf 1 oder 0, indem wir die angegebene Operation jede Runde ausführen.

Wir können das Array in jeder Runde sortieren, um in jeder Iteration das maximale Element zu erhalten. Darüber hinaus können wir die Kopfdatenstruktur auch verwenden, um die Leistung des Codes zu verbessern.

Problemstellung – Wir erhalten eine Reihe von Zahlen[]. Wir müssen das Array wie folgt reduzieren.

• Wählen Sie die beiden größten Elemente im Array aus.

• Wenn zwei Elemente gleich sind, löschen Sie die beiden Elemente aus dem Array.

• Wenn zwei Elemente nicht identisch sind, löschen Sie die beiden Elemente aus dem Array und fügen Sie abs(first − seconds) in das Array ein.

Drucken Sie das letzte Element des Arrays. Wenn das Array leer ist, geben Sie 0 aus.

Beispiel

Eintreten

nums = {5, 9, 8, 3, 2, 5};

Ausgabe

0

Anleitung

• In der ersten Runde nehmen wir 9 und 8 und addieren ihre Differenz zum Array. Daher wird das Array zu [5, 3, 2, 5, 1].

• In der zweiten Runde nehmen wir 5 und 5. Daher wird das Array zu [3, 2, 1].

• In der nächsten Runde nehmen wir 3 und 2. Daher wird das Array zu [1, 1]

• In der letzten Runde nehmen wir 1 und 1. Daher wird das Array leer und wir geben 0 aus.

Eintreten

nums = {5, 5, 5, 5, 5};

Ausgabe

5

Erklärung- Wir löschen zweimal ein 5er-Paar und eine 5 verbleibt im Array.

Eintreten

nums = {4, 8, 7, 6};

Ausgabe

1

Erklärung – Zuerst wählen wir 8 und 7 aus. Daher wird das Array zu [4, 1, 6]. Danach wählen wir 4 und 6 aus. Daher wird das Array zu [1, 2]. Im letzten Vorgang wird das Array zu [1].

Methode 1

Bei dieser Methode durchlaufen wir das Array, bis die Größe des Arrays 1 oder 0 wird. In jeder Iteration sortieren wir das Array und führen die angegebene Operation für die ersten beiden Elemente des sortierten Arrays aus. Abschließend drucken wir die Ausgabe basierend auf der Array-Größe.

Algorithmus

Schritt 1- Speichern Sie die Größe des Arrays in der Variablen „len“.

Schritt 2 – Beginnen Sie mit dem Durchlaufen des Arrays mithilfe einer While-Schleife.

Schritt 3 – Verwenden Sie die Methode sort() in einer Schleife, um das Array umgekehrt zu sortieren.

Schritt 4 – Holen Sie sich das erste und zweite Element des Arrays. Berechnen Sie außerdem die Differenz zwischen dem ersten und zweiten Element des Arrays.

Schritt 5− Wenn die Differenz 0 beträgt, löschen Sie die ersten beiden Elemente des Arrays und reduzieren Sie „len“ um 2. Wenn die Differenz nicht 0 ist, löschen Sie die ersten beiden Elemente und dekrementieren Sie „len“ minus 1.

Schritt 6- Wenn schließlich die Größe des Arrays 0 ist, geben Sie 0 zurück. Andernfalls wird das erste Element des Arrays zurückgegeben.

Beispiel

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    int len = nums.size();
    int p = 0;
    while (len > 1) {
        // Sort array in reverse order
        sort(nums.begin(), nums.end(), greater<int>());
        // Take the first and second elements of the array
        int a = nums[0];
        int b = nums[1];
        // Take the difference between the first and second element
        int diff = a - b;
        if (diff == 0) {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            len -= 2;
        } else {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            nums.push_back(diff);
            len -= 1;
        }
    }
    // When the size of the array is 0
    if (nums.size() == 0)
        return 0;
    return nums[0];
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}

Ausgabe

The last remaining element after performing the given operations is 0

Zeitkomplexität – O(N*NlogN), wobei O(N) zum Durchlaufen des Arrays und O(NlogN) zum Sortieren des Arrays in jeder Iteration verwendet wird.

Raumkomplexität – O(N) zum Sortieren des Arrays.

Methode 2

Bei dieser Methode verwenden wir die Prioritätswarteschlange, die die Heap-Datenstruktur implementiert. Es speichert Elemente immer in sortierter Reihenfolge. So können wir die ersten beiden größten Elemente problemlos entfernen.

Algorithmus

Schritt 1- Definieren Sie „p_queue“, sogenannte Prioritätswarteschlange.

Schritt 2 – Fügen Sie alle Array-Elemente in die Prioritätswarteschlange ein.

Schritt 3 – Iterieren Sie, bis die Prioritätswarteschlangengröße größer als 1 ist.

Schritt 4 – Löschen Sie nacheinander die ersten beiden Elemente der Prioritätswarteschlange.

Schritt 5 – Finden Sie den Unterschied zwischen zwei Elementen.

Schritt 6 – Wenn die Differenz nicht 0 ist, verschieben Sie sie in die Prioritätswarteschlange.

Schritt 7− Wenn die Warteschlangengröße schließlich 0 ist, geben Sie 0 zurück.

Schritt 8 – Andernfalls geben Sie das Element an der Spitze der Warteschlange zurück.

Beispiel

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    // Defining a priority queue
    priority_queue<int> p_queue;
    // Inserting array elements in priority queue
    for (int p = 0; p < nums.size(); ++p)
        p_queue.push(nums[p]);
    // Make iterations
    while (p_queue.size() > 1) {
        // Take the first element from queue
        int first = p_queue.top();
        p_queue.pop();
        // Get the second element from queue
        int second = p_queue.top();
        p_queue.pop();
        // Take the difference of first and second elements
        int diff = first - second;
        if (diff != 0)
            p_queue.push(diff);
    }
    // When queue is empty
    if (p_queue.size() == 0)
        return 0;
    // Return the last remaining element
    return p_queue.top();
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}

Ausgabe

The last remaining element after performing the given operations is 0

Zeitliche Komplexität – Die zeitliche Komplexität des Einfügens und Löschens von Elementen in die Prioritätswarteschlange beträgt O(NlogN).

Raumkomplexität – O(N) zum Speichern von Elementen in der Prioritätswarteschlange.

Die Datenstruktur der Prioritätswarteschlange ist immer nützlich, wenn wir die Array-Daten nach dem Einfügen oder Löschen eines Elements in einer bestimmten Reihenfolge anordnen müssen. Es implementiert die Heap-Datenstruktur und ermöglicht so das Einfügen und Löschen.

Das obige ist der detaillierte Inhalt vonReduzieren Sie ein Array durch die angegebene Operation auf höchstens ein Element. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!