数値がC++のL-RのN範囲にあるかどうかを確認するためのクエリ

この問題では、N個の範囲[L、R]と、それぞれが数値valを含むQ個のクエリが与えられます。私たちのタスクは、クエリを解決して、C++のL-RのN範囲に数値が存在するかどうかを確認するプログラムを作成することです。

問題の説明

LからRまでの整数値を含む[L、R]のタイプのN範囲が与えられます。たとえば、範囲[3、6]には3,4,5,6が含まれます。各クエリで、存在がチェックされるvalが与えられます。プログラムは、valがいずれかの範囲に存在する場合はtrueを返し、そうでない場合はfalseを返します。

問題を理解するために例を見てみましょう

入力 ：ranges [N] ={{2、4}、{6,7}、{9、12}}

Q =3

クエリ={1、7、10}

出力 ：存在しない

プレゼント

プレゼント

説明

クエリ1の場合：番号1はどの範囲にも存在しません。

クエリ2の場合：番号7は{6、7}の範囲にあります。

クエリ1の場合：数値10は{9、12}の範囲にあります。

ソリューションアプローチ

valがいずれかの範囲に存在するかどうかを確認する必要があるため、すべての範囲に対応するvalを確認する必要があります。このために、ハッシュマップを使用します。範囲のLとRを別々に保存してから、binarysearchアルゴリズムを使用して検索すると、ソリューションが簡単になります。

例

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
unordered_map<int, int> mpp;
void initialiseMap(int a[][2], int n){
   for (int i = 0; i < n; i++) {
      v.push_back(a[i][0]);
      mpp[a[i][0]] = 1;
      v.push_back(a[i][1]);
      mpp[a[i][1]] = 2;
   }
   sort(v.begin(), v.end());
}
bool isElementPresent(int val) {
   int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
   if (v[ind] == val)
      return true;
   else {
      if (mpp[v[ind]] == 2)
         return true;
      else
         return false;
   }
}
int main(){
   int arr[][2] = {{2, 4}, {6,7}, {9, 12}};
   int n = 3;
   int Q = 3;
   int query[] = { 1, 7, 10 };
   initialiseMap(arr, n);
   for(int i = 0; i < Q; i++){
      cout<<"For Query "<<(i+1);
      if(isElementPresent(query[i]))
         cout<<": The given digit "<<query[i]<<" is present in one of the given ranges\n";
      else
         cout<<": The given digit "<<query[i]<<" is not present in any of the given ranges\n";
   }
   return 0;
}

出力

For Query 1: The given digit 1 is not present in any of the given ranges
For Query 2: The given digit 7 is present in one of the given ranges
For Query 3: The given digit 10 is present in one of the given ranges