查询以检查数字是否在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 生日广州男生祝福语简短