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