Écrire des requêtes supérieures et non inférieures à l'aide de C++

Dans cet article, on nous pose une question, un tableau, et il y a deux types de requêtes auxquelles répondre.

• Type 0 - Nous devons compter le nombre d'éléments supérieur ou égal à x (valeur donnée).
• Type 1 - Nous devons compter le nombre d'éléments strictement supérieur à x (valeur donnée).

Voici donc un exemple simple -

Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3
   Query 1: 0 50
   Query 2: 1 40
   Query 3: 0 30
Output :
   0
   1
   3
Explanation:
x = 50, q = 0 : No elements greater than or equal to 50.
x = 40, q = 1 : 45 is greater than 40.
x = 30, q = 0 : three elements 30, 40, 45 are greater than or equal to 30.

Façons de trouver la solution

Il existe deux méthodes différentes que nous pouvons utiliser pour trouver la solution. Nous allons d’abord utiliser une solution par force brute, puis vérifier si elle fonctionne pour des contraintes plus élevées. Sinon, nous continuons à optimiser notre solution.

Solution par force brute

Dans cette méthode, nous allons parcourir le tableau pour toutes les q requêtes qui satisfont à la condition donnée et trouverons le nombre qui satisfait à la condition.

Exemple

#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
   int count = 0; // answer
   if(!type) { // when type 0 query is asked
      for(int i = 0; i < n; i++) {
         if(arr[i] >= val)
            count++;
      }
   } else { // when type 1 query is asked
      for(int i = 0; i < n; i++) {
         if(arr[i] > val)
            count++;
      }
   }
   cout << count << "\n";
}
int main() {
   int ARR[] = { 10, 15, 30, 40, 45 };
   int n = sizeof(ARR)/sizeof(ARR[0]); // size of our array
   query(ARR, n, 0, 50); // query 1
   query(ARR, n, 1, 40); // query 2
   query(ARR, n, 0, 30); // query 3
   return 0;
}

Output

0
1
3

Dans la méthode ci-dessus, nous parcourons simplement le tableau et calculons la réponse à la requête ; cette méthode est valide pour l'exemple donné, mais si des contraintes plus élevées sont rencontrées, cette méthode échouera car la complexité temporelle totale du programme est O(N*Q), où N est la taille du tableau et Q est le nombre de requêtes, nous allons donc maintenant optimiser cette approche afin qu'elle fonctionne pour des contraintes plus élevées.

Méthode efficace

Dans cette méthode, nous utiliserons la recherche binaire pour trouver les limites supérieure et inférieure d'une valeur donnée. Nous trions d'abord le tableau à l'aide de la recherche binaire, puis appliquons nos fonctions de limites inférieure et supérieure si nécessaire.

Exemple

#include <bits/stdc++.h>

using namespace std;
void lowerbound(int *arr, int n, int val) {
   int l = -1, r = n;
   while(r - l > 1) { // binary searching the answer
      int mid = (l+r)/2;
      if(arr[mid] >= val)
         r = mid;
      else
         l = mid;
   }
   if(r == n) // if r is unmoved then it means there is no element that satisfy the condition
      cout << "0\n";
   else
      cout << n - r << "\n";
}
void upperbound(int *arr, int n, int val) {
   int l = -1, r = n;
   while(r - l > 1) { // binary searching the answer
      int mid = (l+r)/2;
      if(arr[mid] > val)
         r = mid;
      else
         l = mid;
   }
   if(r == n)// if r is unmoved then it means there is no element that satisfy the condition
      cout << "0\n";
   else
      cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
   if(!type) // if type == 0 we call lower bound function
      lowerbound(arr, n, val);
   else // if type == 1 we call upperbound function
      upperbound(arr, n, val);
}
int main() {
   int arr[] = { 1, 2, 3, 4 };
   int n = sizeof(arr)/sizeof(arr[0]); // size of our array
   sort(arr, arr+n); // sorting the array
   query(arr, n, 0, 5); // query 1
   query(arr, n, 1, 3); // query 2
   query(arr, n, 0, 3); // query 3
   return 0;
}

Sortie

0
1
2

Le code ci-dessus utilise la recherche binaire, ce qui réduit considérablement la complexité temporelle. Par conséquent, notre complexité finale est O(NlogN), où N est la taille du tableau.

Explication du code ci-dessus

Dans cette méthode, nous utiliserons la recherche binaire pour trouver les limites supérieure et inférieure d'une valeur donnée. Maintenant, pour la recherche binaire, nous trions d'abord le tableau car il ne fonctionne que sur un tableau trié. Nous créons une fonction de limite inférieure et une fonction de limite supérieure pour nous aider à trouver le premier nombre qui satisfait aux conditions de type 0 et de type 1. Nous avons maintenant le tableau trié. Nous trouvons le premier nombre qui satisfait la condition, donc l'élément après cet élément satisfait également la condition, nous imprimons donc la différence entre cet élément et l'index de N (la taille du tableau).

Conclusion

Dans cet article, nous avons résolu le problème de la résolution de requêtes supérieures et non inférieures à l'aide de la recherche binaire. Nous avons également appris un programme C++ pour ce problème et notre approche complète pour le résoudre (à la fois triviale et efficace). Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que vous avez trouvé cet article utile.

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!