資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告