Schreiben Sie mit C++ einen Code, um die Anzahl der Subarrays mit denselben Mindest- und Höchstwerten zu ermitteln

In diesem Artikel werden wir C++ verwenden, um das Problem zu lösen, die Anzahl der Unterarrays zu ermitteln, deren Maximal- und Minimalwert gleich sind. Hier ist ein Beispiel für dieses Problem –

Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.

Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same.

Wie man es löst

Als Beispiel können wir sagen, dass eine minimale Anzahl von Unterarrays gebildet werden kann, indem dieselben minimalen und maximalen Elemente verwendet werden, die der Größe des Arrays entsprechen. Die Anzahl der Subarrays kann größer sein, wenn die fortlaufenden Nummern gleich sind.

Wir können also die Methode verwenden, jedes Element zu durchlaufen und zu prüfen, ob seine fortlaufenden Nummern gleich sind. Wenn unterschiedliche Nummern gefunden werden, unterbrechen Sie die innere Schleife.

Jedes Mal, wenn die innere Schleife endet oder unterbrochen wird, wird die Ergebnisvariable erhöht und schließlich wird die Ergebnisvariable angezeigt.

p>

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[ ] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = n, count =0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if(a[i]==a[j])
                count++;
            else
                break;
        }
        result+=count;
        count =0;
    }
    cout << "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

Ausgabe

Number of subarrays having minimum and maximum elements same: 9
Time complexity = O(n<sup>2</sup>).

Erklärung des obigen Codes

In diesem Code verwenden wir die Variable n, um die Größe des Arrays zu speichern, Ergebnis = n, da mindestens n Unterarrays gebildet werden können und die gleiche Anzahl berechneter Zählung.

Die äußere Schleife wird verwendet, um jedes Element im Array zu verarbeiten. Die innere Schleife wird verwendet, um herauszufinden, wie viele aufeinanderfolgende identische Zahlen nach dem Indexelement vorhanden sind, und am Ende der inneren Schleife wird die Zählvariable zusammen mit der Ergebnisvariablen erhöht. Abschließend wird die in der Ergebnisvariablen gespeicherte Ausgabe angezeigt.

Effiziente Methode

Bei dieser Methode durchlaufen wir jedes Element und suchen für jedes Element, wie viele aufeinanderfolgende gleiche Zahlen es gibt. Für jede gefundene identische Zahl erhöhen wir die Zählvariable und wenn eine andere Zahl gefunden wird, ermitteln wir mithilfe der Formel "n = n*(n+1)/2", wie viele Unterarrays gebildet werden können. Erhöhen Sie die Ergebnisvariable.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = 0;
    int count =1,temp=a[0];
    for (int i = 1; i < n; i++) {
        if (temp==a[i]){
            count++;
        }
        else{
            temp=a[i];
            result = result + (count*(count+1)/2);
            count=1;
        }
    }
    result = result + (count*(count+1)/2);
    cout <<  "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

Ausgabe

Number of subarrays having minimum and maximum elements same: 9
Time complexity : O(n)

Obenige Codebeschreibung

In diesem Code speichern wir den 0. Index des Arrays in der temporären Variablen und starten die Schleife ab Index 1. Wir prüfen, ob die temporäre Variable mit dem Element am aktuellen Index übereinstimmt und erhöhen die Anzahl um 1 für die gleiche gefundene Zahl. Wenn die temporäre Variable nicht dem Indexelement entspricht, ermitteln wir die Kombination von Subarrays, die durch Zählen derselben Zahl abgeleitet werden können, und speichern das Ergebnis in der Ergebnisvariablen. Wir ändern den temporären Wert auf den aktuellen Index und setzen den Zähler auf 1 zurück. Abschließend zeigen wir die in der Ergebnisvariablen gespeicherte Antwort an.

Fazit

In diesem Artikel haben wir das Problem gelöst, die Anzahl der Subarrays zu ermitteln, deren minimale und maximale Elemente gleich sind. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonSchreiben Sie mit C++ einen Code, um die Anzahl der Subarrays mit denselben Mindest- und Höchstwerten zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!