查询以检查数字是否在C ++中的LR的N个范围内
在此问题中，我们给了N个范围[L，R]和Q个查询，每个查询都包含一个数字val。我们的任务是创建一个程序来解决查询，以检查数字是否在C++中的LR的N个范围内。
问题描述
给定N个类型为[L，R]的范围，其中包含从L到R的整数值，例如，范围[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，然后使用二进制搜索算法进行搜索将使解决方案变得容易。
示例
#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
热门推荐
10 儿子立冬祝福语简短独特
11 对当兵的祝福语简短
12 侄儿高考试祝福语简短
13 伴郎红包祝福语朋友简短
14 媳妇生日简短祝福语朋友
15 公司年会祝福语简短最好
16 元旦感恩祝福语简短大全
17 红包祝福语简短10字
18 周六早晨祝福语简短