Programme C++ pour compter le nombre d'éléments du tableau qui sont supérieurs à tous les éléments à sa gauche et qui ont au moins K éléments à sa droite

Une chaîne est un objet qui représente une séquence de caractères de données. Les chaînes sont des conteneurs de données toujours représentés au format texte. Il est également utilisé pour les opérations de concept, de comparaison, de fractionnement, de jointure, de remplacement, de découpage, de longueur, d'internement, d'égalité, de comparaison et de sous-chaîne. Les K éléments les plus grands (ou les plus petits) d'un tableau à l'aide de l'algorithme de partitionnement de tri rapide.

Il s'agit d'un tableau R[] contenant N entiers différents. La tâche consiste à trouver cet élément spécifique qui est strictement supérieur à tous les éléments qui le précèdent et strictement supérieur à au moins K éléments à sa droite. Le problème indique qu'un tableau arr[ ] (tableau R) est constitué de N éléments distincts et d'un entier K, nous devons trouver le nombre d'éléments qui sont supérieurs à tous les éléments sur son côté gauche et avoir au moins K éléments sur son côté droit ; .

Input: R[] = {16,07,10,22,2001,1997}, K = 3
Output: 16
Therefore, the count is 2.

Il existe deux façons de trouver des éléments de tableau supérieurs à tous les éléments de gauche et au moins K éléments à droite.

• Méthode naïve - C'est le moyen le plus simple de parcourir un tableau spécifique. Dans cette méthode, nous devons parcourir tous les éléments vers la gauche pour vérifier s'ils sont plus petits. Sinon, déplacez-vous vers la droite et vérifiez si les K éléments les plus petits sont plus petits. Pour cette approche, la complexité temporelle est O(N2) et l’espace auxiliaire est O(1).

• Méthode efficace - Il s'agit d'un processus d'optimisation qui peut être effectué avec un BST auto-équilibré. Parcourez le tableau un par un de droite à gauche à travers l’arborescence AVL. AVL Tree génère un tableau countSmaller[]. Ici, la complexité temporelle est O(NlogN) et l'espace auxiliaire est O(N). Pour chaque élément qui satisfait à la condition, incrémentez le nombre.

Trouvons le nombre d’éléments du tableau qui est supérieur à tous les éléments à sa gauche et à au moins K éléments à sa droite.

Algorithme pour compter les éléments du tableau supérieurs à tous les éléments :-

Dans cet algorithme, nous suivrons le processus étape par étape pour compter le nombre d'éléments du tableau. Avec cela, nous allons construire du code C++ pour trouver le plus grand élément parmi tous les éléments.

• Étape 1 – Commencer.

• Étape 2 - Parcourez le tableau de droite à gauche.

• Étape 3 - Insérez tous les éléments dans l'arborescence AVL.

• Étape 4 - Générez un tableau countSmaller[] en utilisant l'arborescence AVL.

• Étape 5 - Il contient le nombre du plus petit élément à droite de chaque élément du tableau.

• Étape 6 - Parcourez le tableau et trouvez chaque élément.

• Étape 7 - Vérifiez s'il s'agit de la valeur maximale obtenue jusqu'à présent et si countSmaller[i] est supérieur ou égal à K.

• Étape 8 - Si la condition est remplie, augmentez le nombre.

• Étape 9 - Imprimez la valeur finale du nombre comme réponse.

• Étape 10 - Résiliation.

Grammaire

for (i = k; i < array.length; i++){
minIndex = 0;
for (int j = 0; j < k; j++){
   if(array[j] < array[minIndex]){
      minIndex = j;
      array[minIndex] = array[j];
   }
}
if (array[minIndex] < array[i]){
   int temp = array[minIndex];
   array[minIndex] = array[i];
   array[i] = temp;
}

Voici un tableau d'entiers num, l'entier est K. Il renverra le Kième élément du tableau. Nous devons le résoudre en complexité temporelle O(n).

Méthode

• Méthode 1 - Trouvez les K éléments les plus grands (ou les plus petits) en utilisant le tri.

• Méthode 2 - Moyen efficace pour trouver les K éléments les plus grands (ou les plus petits) d'un tableau.

Trouver K éléments les plus grands (ou les plus petits) en utilisant le tri

Nous pouvons obtenir le résultat de ce problème en triant. Voici les étapes -

• Triez les éléments par ordre décroissant.

• Imprimez les premiers K nombres de ce tableau trié.

Exemple 1

#include <bits/stdc++.h>
using namespace std;
void kLargest(int arr[], int a, int b){
   sort(arr, arr + a, greater<int>());
   for (int i = 0; i < b; i++)
   cout << arr[i] << " ";
}
int main(){
   int arr[] = { 10, 16, 07, 2001, 1997, 2022, 50 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   kLargest(arr, n, k);
}
</int>

Sortie

2022 2001 1997 

Un moyen efficace de trouver les K éléments les plus grands (ou les plus petits) d'un tableau

Dans cette méthode, nous suivrons les étapes suivantes pour connaître le résultat -

• Démarrez.

• Parcourez le tableau de droite à gauche.

• Insérez tous les éléments dans l'arborescence AVL.

• Générez le tableau countSmaller[].

• Le nombre du plus petit élément à droite de chaque élément du tableau.

• S'il s'agit de la valeur maximale, countSmaller[i] est supérieur ou égal à K.

• Ensuite, augmentez le nombre.

• Imprimez la valeur.

• La fin.

Exemple 2

#include <bits/stdc++.h>
using namespace std;
struct node {
   int key;
   struct node* left;
   struct node* right;
   int height;
   int size;
};
int max(int a, int b);
int height(struct node* N){
   if (N == NULL)
   return 0;
   return N->height;
}
int size(struct node* N){
   if (N == NULL)
   return 0;
   return N->size;
}
int max(int a, int b){
   return (a > b) ? a : b;
}
struct node* newNode(int key){
   struct node* node
   = (struct node*)
   malloc(sizeof(struct node));
   node->key = key;
   node->left = NULL;
   node->right = NULL;
   node->height = 1;
   node->size = 1;
   return (node);
}
struct node* rightRotate(struct node* y){
   struct node* x = y->left;
   struct node* T2 = x->right;
   x->right = y;
   y->left = T2;
   y->height = max(height(y->left),
   height(y->right))
   + 1;
   x->height = max(height(x->left),
   height(x->right))
   + 1;
   y->size = size(y->left)
   + size(y->right) + 1;
   x->size = size(x->left)
   + size(x->right) + 1;
   return x;
}
struct node* leftRotate(struct node* x){
   struct node* y = x->right;
   struct node* T2 = y->left;
   y->left = x;
   x->right = T2;
   x->height = max(height(x->left),
   height(x->right))
   + 1;
   y->height = max(height(y->left),
   height(y->right))
   + 1;
   x->size = size(x->left)
   + size(x->right) + 1;
   y->size = size(y->left)
   + size(y->right) + 1;
   return y;
}
int getBalance(struct node* N){
   if (N == NULL)
   return 0;
   return height(N->left)
   - height(N->right);
}
struct node* insert(struct node* node, int key,
int* count){
   if (node == NULL)
      return (newNode(key));
   if (key < node->key)
      node->left = insert(node->left, key, count);
   else {
      node->right = insert(node->right, key, count);
      *count = *count + size(node->left) + 1;
   }
   node->height = max(height(node->left),
   height(node->right))
   + 1;
   node->size = size(node->left)
   + size(node->right) + 1;
   int balance = getBalance(node);
   if (balance > 1 && key < node->left->key)
   return rightRotate(node);
   if (balance < -1 && key > node->right->key)
   return leftRotate(node);
   if (balance > 1 && key > node->left->key) {
      node->left = leftRotate(node->left);
      return rightRotate(node);
   }
   if (balance < -1 && key < node->right->key) {
      node->right = rightRotate(node->right);
      return leftRotate(node);
   }
   return node;
}
void constructLowerArray(int arr[],
int countSmaller[],
int n){
   int i, j;
   struct node* root = NULL;
   for (i = 0; i < n; i++)
      countSmaller[i] = 0;
   for (i = n - 1; i >= 0; i--) {
      root = insert(root, arr[i], &countSmaller[i]);
   }
}
int countElements(int A[], int n, int K){
   int count = 0;
   int* countSmaller = (int*)malloc(sizeof(int) * n);
   constructLowerArray(A, countSmaller, n);
   int maxi = INT_MIN;
   for (int i = 0; i <= (n - K - 1); i++) {
      if (A[i] > maxi && countSmaller[i] >= K) {
         count++;
         maxi = A[i];
      }
   }
   return count;
}
int main(){
   int A[] = { 16, 10, 2022, 1997, 7, 2001, 0 };
   int n = sizeof(A) / sizeof(int);
   int K = 3;
   cout << countElements(A, n, K);
   return 0;
}

Sortie

2

Conclusion

Nous savons donc comment écrire du code C++ pour compter le nombre d'éléments de tableau supérieur à tous les éléments à sa gauche et au moins K éléments à sa droite.

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!