Ermitteln Sie beim Programmieren in C++ die Anzahl der Subarrays mit m ungeraden Zahlen

Wenn Sie jemals C++ verwendet haben, müssen Sie wissen, was Subarrays sind und wie nützlich sie sind. Wie wir alle wissen, können wir in C++ mehrere mathematische Probleme leicht lösen. In diesem Artikel erklären wir daher, wie Sie mithilfe dieser Subarrays in C++ die vollständigen Informationen von M ungeraden Zahlen finden.

In diesem Problem müssen wir eine Anzahl von Subarrays und ganzen Zahlen m finden, die aus dem gegebenen Array bestehen, wobei jedes Subarray genau m ungerade Zahlen enthält. Hier ist ein einfaches Beispiel für diesen Ansatz –

Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }

Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

Erster Ansatz

Bei diesem Ansatz werden alle möglichen Unterarrays aus dem gegebenen Array generiert und jedes Unterarray wird überprüft, ob es genau m ungerade Zahlen hat. Dies ist eine einfache Generierungs- und Suchmethode mit einer Zeitkomplexität von O(n²).

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // n is size of array, m numbers to be find in subarrays,
                              // count is number of subarray with m odd numbers
    for (int i = 0; i < n; i++){ // outer loop to process each element.
        int odd = 0;
        for (int j = i; j < n; j++) {// inner loop to find subarray with m number
            if (a[j] % 2)
                odd++;
            if (odd == m) // if odd numbers become equals to m.
                count++;
        }
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

Ausgabe

Number of subarrays with n numbers are: 6

Oben Codebeschreibung

In diesem Code verwenden wir verschachtelte Schleifen, um m ungerade Unterarrays zu finden. Die äußere Schleife wird verwendet, um „i“ zu erhöhen, das zur Verarbeitung jedes einzelnen verwendet wird Element im Array.

Die innere Schleife wird verwendet, um das Subarray zu finden und die Elemente zu verarbeiten, bis der ungerade Zähler m erreicht, den Ergebniszählerzähler für jedes gefundene Subarray zu erhöhen und schließlich das im Zähler gespeicherte Ergebnis auszugeben.

Zweite Methode

Eine andere Methode ist zu Erstellen Sie ein Array, um die Anzahl „i“ ungerader Präfixe zu speichern, verarbeiten Sie jedes Element und erhöhen Sie die Anzahl ungerader Zahlen jedes Mal, wenn eine ungerade Zahl gefunden wird.

Wenn die Anzahl der ungeraden Zahlen m überschreitet oder gleich ist, fügen Sie die Zahl an der Position (ungerade - m) im Präfix-Array hinzu.

Wenn die ungerade Zahl größer oder gleich m wird, zählen wir die Anzahl der gebildeten Unterarrays, bis der Index und die Zahl „ungerade – m“ zur Zählvariablen hinzugefügt werden. Nachdem jedes Element verarbeitet wurde, wird das Ergebnis in der Zählvariablen gespeichert.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // outer loop to process every element of array
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1;    // implementing value at odd index in prefix_array[ ]
        // if array element is odd then increment odd variable
        if (array[i] % 2 == 0)
            odd++;
        // if Number of odd element becomes equal or greater than m
        //  then find the number of possible subarrays that can be formed till the index.
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

Ausgabe

Number of subarrays with n numbers are: 6

Erklärung des obigen Codes

Arrays und Variablen mit Startwerten initialisieren -

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };

Hier initialisieren wir Variable n mit der Größe des Arrays und Variable m mit der Anzahl der ungeraden Zahlen Wir suchen, initialisieren count mit 0, um die Anzahl möglicher Unterarrays beizubehalten, initialisieren ungerade Zahlen mit 0, initialisieren Variable n mit prefix_array der Größe n + 1 0.

Schleifen verstehen

for (i = 0; i < n; i++){
   prefix_array[odd] = prefix_array[odd] + 1;
   if (array[i] % 2 == 0)
      odd++;
      if (odd >= m)
         count += prefix_array[odd - m];
}

In dieser Schleife befinden wir uns in prefix_array [ ] implementiert den Wert an einem ungeraden Index und erhöht dann die ungerade Variable, wenn eine ungerade Zahl gefunden wird. Wir stellen fest, dass, wenn ungerade Variablen gleich oder größer als m sind, die Anzahl der Unterarrays bis zum Index gebildet werden kann.

Schließlich drucken wir die m ungeraden Subarray-Nummern aus, die in der Zählvariablen gespeichert sind, und erhalten die Ausgabe. Fazit Array gefunden Die Anzahl des Arrays. Die zeitliche Komplexität dieses Codes beträgt O(n2).

Effiziente Methode: Durchlaufen Sie jedes Element des Arrays, erstellen Sie ein Präfix-Array und verwenden Sie dann die Hilfe des Präfix-Arrays. Die zeitliche Komplexität dieses Codes beträgt O(n).

• Ich hoffe, dieser Artikel hilft Ihnen, das Problem und die Lösung zu verstehen.

Das obige ist der detaillierte Inhalt vonErmitteln Sie beim Programmieren in C++ die Anzahl der Subarrays mit m ungeraden Zahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!