Berechnen Sie das Subarray der Länge K, dessen Mittelwert den Median des angegebenen Arrays überschreitet

Der Ausdruck „K-Länge-Subarray“ gilt für zusammenhängende Subarrays mit genau K Elementen. Die Beherrschung und Verwendung von Subarrays ist für die Lösung verschiedener Probleme in Bereichen wie dynamischer Programmierung, Computergeometrie und Datenanalyse von entscheidender Bedeutung.

Ein weiteres wichtiges Konzept bei Array-Operationen und Statistiken ist der Median. Der Median eines Arrays stellt den Wert in der Mitte dar, wenn die Elemente in aufsteigender Reihenfolge sortiert werden. Bei einer geraden Anzahl von Elementen ist der Median der Durchschnitt der beiden Zentralwerte. Der Median stellt ein dauerhaftes Maß für die zentrale Tendenz dar, da er weniger anfällig für Extremwerte oder Ausreißer ist als der Mittelwert.

In diesem Artikel wird versucht, die Herausforderung zu untersuchen, die Anzahl der Subarrays der K-Länge in einem bestimmten Array zu bestimmen, deren Mittelwert den Median überschreitet. Indem wir die Beziehung zwischen dem Mittelwert und dem Median eines Datensatzes verstehen, können wir uns mit dieser Herausforderung befassen und effiziente Techniken zu ihrer Lösung entwickeln. Begleiten Sie uns, wenn wir die Problemstellung analysieren, Schlüsselkonzepte untersuchen und algorithmisch effizient die Anzahl der in einem Array erforderlichen Subarrays der K-Länge berechnen.

Grammatik

Sortieren Sie die Elemente in einem Array in aufsteigender Reihenfolge.

sort(begin(array), end(array))

Deklarieren Sie einen Vektor aus ganzen Zahlen.

vector<int> vec
</int>

Deklarieren Sie ein Integer-Array

int arr[]

Grundlegende for-Schleifensyntax in C++.

for(int i=0; i<size; ++i)

Algorithmus des Quellcodes

• Lesen Sie das Eingabearray und seine Größe.

• Berechnen Sie den Median des angegebenen Arrays.

• Berechnen Sie für jedes Unterarray der Länge K den Durchschnitt.

• Vergleichen Sie den Mittelwert mit dem Median.

• Statistik-Subarrays, deren Mittelwert den Median übersteigt.

Methode 1: Brute-Force-Cracking

Methode 1 stellt eine einfache Lösung für die Herausforderung dar, die Anzahl der Subarrays der Länge K zu bestimmen, deren Mittelwert den Median eines bestimmten Arrays überschreitet. Zunächst wird das Eingabearray sortiert und der Median berechnet. Anschließend durchläuft das Programm alle möglichen Subarrays der K-Länge und berechnet ihren Durchschnitt durch Aggregation ihrer Komponenten. Wenn der Mittelwert des Subarrays den Median überschreitet, wird die Anzahl erhöht. Schließlich gibt der Code die Anzahl solcher Subarrays zurück.

Algorithmus

• Berechnen Sie den Median des angegebenen Arrays.

• Iterieren Sie über alle möglichen Subarrays der Länge K.

• Berechnen Sie den Durchschnitt jedes Unterarrays.

• Wenn der Mittelwert des Subarrays größer als der Median ist, erhöhen Sie die Anzahl.

Beispiel 1

Der folgende Code folgt dem zuvor in diesem Artikel erwähnten Brute-Force-Ansatz. Zunächst wird das Eingabearray sortiert und der Median berechnet. Anschließend iteriert es über alle möglichen Subarrays der Länge K und berechnet deren Durchschnitt durch Summieren ihrer Elemente. Wenn der Mittelwert des Subarrays größer als der Median ist, wird die Anzahl erhöht. Schließlich gibt der Code die Anzahl solcher Subarrays zurück.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int countSubarrays(vector<int> &arr, int n, int k) {
   int count = 0;
   double median;
   sort(arr.begin(), arr.end());
   median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];

   for (int i = 0; i <= n - k; i++) {
      double sum = 0;
      for (int j = i; j < i + k; j++) {
         sum += arr[j];
      }
      if (sum / k > median) {
         count++;
      }
   }
   return count;
}

int main() {
   vector<int> arr = {1, 5, 6, 7, 9};
   int n = arr.size();
   int k = 3;
   int result = countSubarrays(arr, n, k);
   cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
   return 0;
}

Ausgabe

Number of K-length subarrays with average exceeding median: 1

Methode 2: Optimierungsmethode

Methode 2 ist eine elegante Lösung für das Problem der Bestimmung der Anzahl von Subarrays der Länge K, deren Mittelwert den Median eines bestimmten Arrays überschreitet. Zunächst wird das Eingabearray sortiert und der Median berechnet. Anschließend wird das Präfixsummen-Array berechnet, das zur Bestimmung der Summe jedes K-Längen-Subarrays verwendet wird. Der Algorithmus iteriert über alle möglichen Subarrays der Länge K, berechnet ihren Durchschnitt mithilfe des Präfix-Summenarrays und vergleicht ihn mit dem Median.

Wenn der Mittelwert des Subarrays den Median überschreitet, wird die Anzahl erhöht. Abschließend gibt das Programm die Anzahl solcher Subarrays zurück. Dieser Ansatz ist effizienter als der erste Ansatz, da er Präfixsummen-Arrays verwendet, um die Summe jedes K-Längen-Subarrays zu berechnen, wodurch die Laufzeitkomplexität verringert wird.

Algorithmus

• Berechnen Sie den Median des angegebenen Arrays.

• Berechnen Sie Präfix und Array.

• Iterieren Sie über alle möglichen Subarrays der Länge K.

• Berechnen Sie den Durchschnitt mithilfe von Präfix und Array.

• Wenn der Mittelwert des Subarrays größer als der Median ist, erhöhen Sie die Anzahl.

Beispiel 2

Dieser Algorithmus folgt dem besten zuvor beschriebenen Ansatz. Es nutzt Präfix-Summen-Arrays, um schnell Aggregate für jede Teilmenge der K-Länge zu berechnen. Nachdem die Eingabesequenz sortiert und der Medianwert bestimmt wurde, wird die Präfixsumme berechnet. Das Programm durchläuft dann alle Teilmengen der K-Länge, berechnet ihren Durchschnitt mithilfe des Präfix-Summen-Arrays und vergleicht ihn mit dem Median. Wenn der Mittelwert den Median überschreitet, wird die Anzahl erhöht. Zusammenfassend gibt der Code die Anzahl solcher Teilmengen zurück.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int countSubarrays(vector<int> &arr, int n, int k) {
   int count = 0;
   double median;
   sort(arr.begin(), arr.end());
   median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];

   vector<int> prefix_sum(n);
   prefix_sum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      prefix_sum[i] = prefix_sum[i - 1] + arr[i];
   }

   for (int i = 0; i <= n - k; i++) {
      double sum = (i == 0) ? prefix_sum[i + k - 1] : prefix_sum[i + k - 1] - prefix_sum[i - 1];
      if (sum / k > median) {
         count++;
      }
   }
   return count;
}

int main() {
   vector<int> arr = {1, 5, 6, 7, 9};
   int n = arr.size();
   int k = 3;
   int result = countSubarrays(arr, n, k);
   cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
   return 0;
}

Ausgabe

Number of K-length subarrays with average exceeding median: 1

Fazit

In diesem Artikel haben wir zwei Möglichkeiten zur Berechnung von Subarrays der Länge K, deren Mittelwert den Median eines bestimmten Arrays überschreitet, mit C++ besprochen. Die erste Methode ist die Brute-Force-Methode, die alle möglichen Subarrays der Länge K durchläuft und deren Durchschnitt berechnet. Die zweite Methode ist eine Optimierungsmethode, die Präfixe und Arrays verwendet, um den Durchschnitt effizienter zu berechnen. Beide Codes werden bereitgestellt und können ausgeführt werden, um die erforderliche Anzahl von Subarrays zu finden.

Das obige ist der detaillierte Inhalt vonBerechnen Sie das Subarray der Länge K, dessen Mittelwert den Median des angegebenen Arrays überschreitet. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!