数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 中检查数字是否位于 N 个 L-R 范围内的查询
在这个问题中，我们给定 N 个范围 [L, R] 和 Q 个查询，每个查询包含一个数字 val。我们的任务是创建一个程序来解决 C++ 中检查数字是否位于 N 个 L-R 范围内的查询。
问题描述
我们给定 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} 中。
对于查询 3：数字 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
更新于：2020年10月9日
413 次浏览
广告