C++ を使用した「以上」および「以上」クエリの作成

この記事では、配列が与えられた質問が与えられ、答える必要があるクエリは 2 種類あります。

• タイプ 0 - x (指定された値) 以上の要素の数を数える必要があります。
• タイプ 1 - x (指定された値) よりも厳密に大きい要素の数をカウントする必要があります。

ここに簡単な例を示します。

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.

解決策を見つける方法

解決策を見つけるには 2 つの異なる方法を使用できます。まず総当りのソリューションを使用し、それがより高い制約に対して機能するかどうかを確認します。そうでない場合は、ソリューションの最適化を続けます。

ブルートフォースソリューション

この方法では、指定された条件を満たすすべての q クエリの配列を反復処理し、条件を満たす数値を見つけます。

Example

#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

上記のメソッドでは、配列をループしてクエリに対する答えを計算するだけです。このメソッドは、指定された例に対して有効です。ただし、このアプローチは、より高い制約に遭遇すると失敗します。プログラムの合計時間計算量は O(N*Q) (N は配列のサイズ、Q はクエリの数) であるためです。そこで、この方法を最適化します。より高度な制約に適用できるようにします。

効率的な方法

この方法では、二分探索を使用して、指定された値の上限と下限を見つけます。まず二分探索を使用して配列を並べ替え、次に必要に応じて下限関数と上限関数を適用します。

例

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

出力

0
1
2

上記のコードではバイナリ検索を使用しているため、時間の複雑さが大幅に軽減されます。したがって、最終的な複雑さは O(NlogN) になります (N は配列のサイズです)。

上記コードの説明

このメソッドでは、二分探索を使用して、指定された値の上限と下限を見つけます。二分探索では、ソートされた配列でのみ機能するため、最初に配列をソートします。タイプ 0 とタイプ 1 の条件を満たす最初の数値を見つけるのに役立つ下限関数と上限関数を作成します。これで、配列がソートされました。条件を満たす最初の数値が見つかると、この要素の後の要素も条件を満たすため、その要素と N のインデックス (配列のサイズ) の差を出力します。

結論

この記事では、二分探索を使用して「以上」および「以上」クエリを解決する問題を解決しました。また、この問題に対する C プログラムと、それを解決するための完全なアプローチ (簡単かつ効率的な) についても学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用した「以上」および「以上」クエリの作成の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。