숫자가 C++에서 L-R의 N 범위에 있는지 확인하는 쿼리

이 문제에서 우리는 각각 숫자 val을 포함하는 N개의 범위 [L, R] 및 Q 쿼리가 제공됩니다. 우리의 임무는 C++에서 L-R의 N 범위에 숫자가 있는지 확인하기 위해 쿼리를 해결하는 프로그램을 만드는 것입니다.

문제 설명

L에서 R까지의 정수 값을 포함하는 [L, R] 유형의 N 범위가 제공됩니다. 예를 들어 범위 [3, 6]에는 3,4,5,6이 포함됩니다. 각 쿼리에서 존재 여부를 확인할 val이 제공됩니다. val이 범위 중 하나에 있으면 프로그램은 true를 반환하고 그렇지 않으면 false를 반환합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 :범위[N] ={{2, 4}, {6,7}, {9, 12}}

Q =3

쿼리 ={1, 7, 10}

출력 :존재하지 않음

발표

발표

설명

쿼리 1의 경우:숫자 1은 범위에 없습니다.

쿼리 2:{6, 7} 범위에 숫자 7이 있습니다.

쿼리 1의 경우:숫자 10은 {9, 12} 범위에 있습니다.

해결 방법

val이 어느 범위에 있는지 확인해야 하므로 모든 범위에 해당하는 val을 확인해야 합니다. 이를 위해 해시맵을 사용합니다. 범위의 L과 R을 별도로 저장한 다음 바이너리 검색 알고리즘을 사용하여 검색하면 솔루션을 쉽게 만들 수 있습니다.

예

#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