Calculer le sous-tableau de longueur K dont la moyenne dépasse la médiane du tableau donné

L'expression "sous-tableau de longueur K" s'applique aux sous-tableaux contigus avec exactement K éléments. La maîtrise et l'utilisation des sous-réseaux sont essentielles pour résoudre une variété de problèmes dans des domaines tels que la programmation dynamique, la géométrie computationnelle et l'analyse des données.

Un autre concept important dans les opérations et les statistiques sur les tableaux est la médiane. La médiane d'un tableau représente la valeur au milieu lorsque les éléments sont triés par ordre croissant. Lorsqu’il y a un nombre pair d’éléments, la médiane est la moyenne des deux valeurs centrales. La médiane constitue une mesure durable de tendance centrale car elle est moins sensible aux valeurs extrêmes ou aberrantes que la moyenne.

Cet article tente d'étudier le défi de déterminer le nombre de sous-tableaux de longueur K dans un tableau donné dont la moyenne dépasse la médiane. En comprenant la relation entre la moyenne et la médiane d’un ensemble de données, nous pouvons approfondir ce défi et développer des techniques efficaces pour le résoudre. Rejoignez-nous pour disséquer l'énoncé du problème, examiner les concepts clés et calculer efficacement de manière algorithmique le nombre de sous-tableaux de longueur K requis dans un tableau.

Grammaire

Triez les éléments d'un tableau par ordre croissant.

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

Déclarez un vecteur d'entiers.

vector<int> vec
</int>

Déclarer un tableau d'entiers

int arr[]

Syntaxe de base de la boucle for en C++.

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

Algorithme du code source

• Lisez le tableau d'entrée et sa taille.

• Calculez la médiane du tableau donné.

• Pour chaque sous-tableau de longueur K, calculez la moyenne.

• Comparez la moyenne avec la médiane.

• Sous-tableaux de statistiques dont la moyenne dépasse la médiane.

Méthode 1 : Fissuration par force brute

La méthode 1 constitue une solution simple au défi de déterminer le nombre de sous-tableaux de longueur K dont la moyenne dépasse la médiane d'un tableau spécifié. Initialement, le tableau d'entrée est trié et la médiane est calculée. Par la suite, le programme parcourt tous les sous-réseaux réalisables de longueur K et calcule leur moyenne en agrégeant leurs composants. Si la moyenne du sous-tableau dépasse la médiane, le décompte est incrémenté. Enfin, le code renvoie le nombre de ces sous-tableaux.

Algorithme

• Calculez la médiane du tableau donné.

• Parcourez tous les sous-tableaux possibles de longueur K.

• Calculez la moyenne de chaque sous-tableau.

• Si la moyenne du sous-tableau est supérieure à la médiane, incrémentez le décompte.

Exemple 1

Le code ci-dessous suit l'approche par force brute mentionnée plus haut dans cet article. Il trie d'abord le tableau d'entrée et calcule la médiane. Il parcourt ensuite tous les sous-tableaux possibles de longueur K et calcule leur moyenne en additionnant leurs éléments. Si la moyenne du sous-tableau est supérieure à la médiane, le décompte est incrémenté. Enfin, le code renvoie le nombre de ces sous-tableaux.

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

Sortie

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

Méthode 2 : Méthode d'optimisation

La méthode 2 est une solution élégante au problème de la détermination du nombre de sous-tableaux de longueur K avec une moyenne dépassant la médiane d'un tableau spécifié. Il trie d'abord le tableau d'entrée et calcule la médiane. Il calcule ensuite le tableau de somme de préfixes, qui est utilisé pour déterminer la somme de chaque sous-tableau de longueur K. L'algorithme parcourt tous les sous-tableaux possibles de longueur K, calcule leur moyenne à l'aide du tableau de somme de préfixes et compare avec la médiane.

Si la moyenne du sous-tableau dépasse la médiane, le décompte est incrémenté. Enfin, le programme renvoie le nombre de ces sous-tableaux. Cette approche est plus efficace que la première approche car elle utilise un tableau de somme de préfixes pour calculer la somme de chaque sous-tableau de longueur K, réduisant ainsi la complexité d'exécution.

Algorithme

• Calculez la médiane du tableau donné.

• Calculez le préfixe et le tableau.

• Parcourez tous les sous-tableaux possibles de longueur K.

• Calculez la moyenne en utilisant le préfixe et le tableau.

• Si la moyenne du sous-tableau est supérieure à la médiane, incrémentez le décompte.

Exemple 2

Cet algorithme suit la meilleure approche décrite précédemment. Il exploite des tableaux de sommes de préfixes pour calculer rapidement des agrégats pour chaque sous-ensemble de longueur K. Une fois la séquence d'entrée triée et la valeur médiane déterminée, la somme des préfixes est calculée. Le programme parcourt ensuite tous les sous-ensembles de longueur K, calcule leur moyenne à l'aide du tableau de somme de préfixes et la compare à la médiane. Si la moyenne dépasse la médiane, le décompte est incrémenté. En résumé, le code renvoie le nombre de ces sous-ensembles.

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

Sortie

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

Conclusion

Dans cet article, nous avons discuté de deux façons de calculer des sous-tableaux de longueur K dont la moyenne dépasse la médiane d'un tableau donné en utilisant C++. La première méthode est la méthode par force brute, qui parcourt tous les sous-tableaux possibles de longueur K et calcule leur moyenne. La deuxième méthode est une méthode d'optimisation qui utilise des préfixes et des tableaux pour calculer la moyenne plus efficacement. Les deux codes sont fournis et peuvent être exécutés pour trouver le nombre requis de sous-tableaux.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!