查询以检查数字是否在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 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短