資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中檢查給定範圍內是否存在給定數字的查詢
在這個問題中，我們給定了一個數組 arr[] 和一些查詢，每個查詢包含三個值 L、R 和 val。我們的任務是建立一個程式來解決 C++ 中檢查給定範圍內是否存在給定數字的查詢。
問題描述 -
為了解決每個查詢，我們需要檢查給定元素 val 是否存在於 L 和 R 之間的給定範圍內。
讓我們舉一個例子來理解這個問題，
**輸入**:arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1}
Q = 3
query = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }}
**輸出**:不存在
存在
存在
解釋
查詢 1：範圍是 [1, 4]，子陣列 = {8, 1, 7, 2}。3 不存在於此子陣列中。
查詢 2：範圍是 [0, 2]，子陣列 = {4, 8, 1}。1 存在於此子陣列中。
查詢 1：範圍是 [4, 7]，子陣列 = {2, 9, 3, 5, 1}。2 存在於此子陣列中。
解決方案方法
解決此問題的一個簡單方法是遍歷子陣列並檢查給定元素是否存在於範圍內。
示例
#include <iostream>
using namespace std;
bool isElementPresent(int arr[], int L, int R, int val){
for(int i = L; i <= R; i++ ){
if(arr[i] == val){
return true;
}
}
return false;
}
int main(){
int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
int Q = 3;
int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(arr, query[i][0], query[i][1], query[i][2]))
cout<<": The given digit "<<query[i][2]<<" is present in the given range\n";
else
cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
}
return 0;
}輸出
For Query 1: The given digit 3 is not present in the given range For Query 2: The given digit 1 is present in the given range For Query 3: The given digit 2 is present in the given range
這種方法使用迴圈，因此時間複雜度為 O(Q * N) 級別。其中 Q 是查詢數。
一個**更好的解決方案方法**可能是使用線段樹來儲存所有可能的數字 (0 - 9)。為了避免節點中的重複元素，我們將使用 set 資料結構（它具有消除重複元素的屬性）。這將有助於我們將每個節點中的元素總數減少到最多 10 個。
然後，對於查詢，我們將檢查元素是否存在於給定範圍內。
示例
#include <bits/stdc++.h>
using namespace std;
set<int> SegTree[36];
void buildSegmentTree(int* arr, int index, int start, int end) {
if (start == end) {
SegTree[index].insert(arr[start]);
return;
}
int middleEle = (start + end) >> 1;
buildSegmentTree(arr, 2 * index, start, middleEle);
buildSegmentTree(arr, 2 * index + 1, middleEle + 1, end);
for (auto it : SegTree[2 * index])
SegTree[index].insert(it);
for (auto it : SegTree[2 * index + 1])
SegTree[index].insert(it);
}
bool isElementPresent(int index, int start, int end, int L, int R, int val){
if (L <= start && end <= R) {
if (SegTree[index].count(val) != 0) {
return true;
}
else
return false;
}
if (R < start || end < L) {
return false;
}
int middleEle = (start + end) >> 1;
bool isPresentInLeftSubArray = isElementPresent((2 * index), start,middleEle, L, R, val);
bool isPresentInRightSubArray = isElementPresent((2 * index + 1),(middleEle + 1), end, L, R, val);
return isPresentInLeftSubArray or isPresentInRightSubArray;
}
int main(){
int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
int n = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
buildSegmentTree(arr, 1, 0, (n - 1));
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(1, 0, (n - 1), query[i][0], query[i][1], query[i][2]))
cout<<": The given digit "<<query[i][2]<<" is present in the given
range\n";
else
cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
}
return 0;
}輸出
For Query 1: The given digit 3 is not present in the given range For Query 2: The given digit 1 is present in the given range For Query 3: The given digit 2 is present in the given range
更新於: 2020年10月9日
287 次檢視
廣告