Schreiben von Größer-als- und nicht-kleiner-als-Abfragen mit C++

In diesem Artikel erhalten wir eine Frage, ein Array und es müssen zwei Arten von Abfragen beantwortet werden.

• Typ 0 – Wir müssen die Anzahl der Elemente zählen, die größer oder gleich x (angegebener Wert) sind.
• Typ 1 – Wir müssen die Anzahl der Elemente zählen, die unbedingt größer als x (angegebener Wert) sind.

Hier ist also ein einfaches Beispiel –

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.

Möglichkeiten, die Lösung zu finden

Es gibt zwei verschiedene Methoden, mit denen wir die Lösung finden können. Zuerst verwenden wir eine Brute-Force-Lösung und prüfen dann, ob sie für höhere Einschränkungen funktioniert. Wenn nicht, optimieren wir unsere Lösung weiter.

Brute-Force-Lösung

In dieser Methode durchlaufen wir das Array für alle q-Abfragen, die die gegebene Bedingung erfüllen, und finden die Zahlen, die die Bedingung erfüllen.

Beispiel

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

Ausgabe

0
1
3

In der obigen Methode iterieren wir einfach über das Array und berechnen die Antwort auf die Abfrage; diese Methode ist für das angegebene Beispiel gültig, aber wenn höhere Einschränkungen auftreten, schlägt diese Methode fehl, weil Die Gesamtzeitkomplexität des Programms beträgt O(N*Q), wobei N die Größe des Arrays und Q die Anzahl der Abfragen ist. Daher werden wir diesen Ansatz nun optimieren, damit er für höhere Einschränkungen funktioniert.

Effiziente Methode

Bei dieser Methode verwenden wir die binäre Suche, um die Ober- und Untergrenzen eines bestimmten Werts zu finden. Wir sortieren das Array zunächst mithilfe der binären Suche und wenden dann nach Bedarf unsere Unter- und Obergrenzenfunktionen an.

Beispiel

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

Ausgabe

0
1
2

Der obige Code verwendet eine binäre Suche, was die zeitliche Komplexität erheblich reduziert. Daher ist unsere endgültige Komplexität O(NlogN), wobei N die Größe des Arrays ist.

Erklärung des obigen Codes

Bei dieser Methode verwenden wir die binäre Suche, um die Ober- und Untergrenzen eines bestimmten Werts zu finden. Bei der binären Suche sortieren wir nun zuerst das Array, da dies nur bei sortierten Arrays funktioniert. Wir erstellen eine Untergrenze und eine Obergrenze, um die erste Zahl zu finden, die die Bedingungen von Typ 0 und Typ 1 erfüllt. Jetzt haben wir das Array sortiert. Wir finden die erste Zahl, die die Bedingung erfüllt, also erfüllt das Element nach diesem Element auch die Bedingung, also geben wir die Differenz zwischen diesem Element und dem Index von N (der Größe des Arrays) aus.

Fazit

In diesem Artikel haben wir das Problem gelöst, Größer-als- und Nicht-Kleiner-als-Abfragen mithilfe der binären Suche zu lösen. Wir haben auch ein C++-Programm für dieses Problem und unseren vollständigen Lösungsansatz (sowohl trivial als auch effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie fanden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonSchreiben von Größer-als- und nicht-kleiner-als-Abfragen mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!