ในปัญหานี้ เราได้ให้อาร์เรย์ arr[] และแบบสอบถามบางรายการประกอบด้วยสามค่า ได้แก่ L และ R และ val งานของเราคือสร้างโปรแกรมเพื่อแก้ปัญหาแบบสอบถามเพื่อตรวจสอบว่าตัวเลขที่ระบุมีอยู่ในช่วงที่กำหนดใน C ++ หรือไม่
คำอธิบายปัญหา−
เพื่อแก้ปัญหาแต่ละคำถาม เราต้องตรวจสอบว่าองค์ประกอบที่กำหนดมีอยู่ในช่วงที่กำหนดระหว่าง L และ R หรือไม่
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล :arr[] ={4, 8, 1, 7, 2, 9, 3, 5, 1}
Q =3
ข้อความค้นหา ={{1, 4, 3}, {0, 2, 1}, {4}4, 7, 2 }}
ผลผลิต :ไม่อยู่
นำเสนอ
นำเสนอ
คำอธิบาย
แบบสอบถาม 1:ช่วงคือ [1, 4], subarray ={8, 1, 7, 2} 3 ไม่มีอยู่ในอาร์เรย์ย่อยนี้
แบบสอบถาม 2:ช่วงคือ [0, 2], subarray ={4, 8, 1} มี 1 อยู่ในอาร์เรย์ย่อยนี้
แบบสอบถาม 1:ช่วงคือ [4, 7], subarray ={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) เพื่อหลีกเลี่ยงองค์ประกอบที่ซ้ำกันในโหนด เราจะใช้โครงสร้างข้อมูลที่ตั้งไว้ (มีคุณสมบัติในการกำจัดองค์ประกอบที่ซ้ำกัน) วิธีนี้จะช่วยเราลดจำนวนองค์ประกอบทั้งหมดในแต่ละโหนดให้เหลือสูงสุด 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
