Trong bài toán này, chúng ta đã đưa ra một mảng arr [] và một số truy vấn, mỗi truy vấn bao gồm ba giá trị, L và R và val. Nhiệm vụ của chúng tôi là tạo một chương trình giải các Truy vấn để kiểm tra xem một chữ số nhất định có nằm trong Dải ô đã cho trong C ++ hay không.
Mô tả vấn đề−
Để giải quyết từng truy vấn, chúng ta cần kiểm tra xem phần tử đã cho val có nằm trong Phạm vi đã cho giữa L và R hay không.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào :arr [] ={4, 8, 1, 7, 2, 9, 3, 5, 1}
Q =3
truy vấn ={{1, 4, 3}, {0, 2, 1}, {4, 7, 2}}
Đầu ra :Không có mặt
Hiện tại
Hiện tại
Giải thích
Truy vấn 1:phạm vi là [1, 4], mảng con ={8, 1, 7, 2}. 3 không có trong mảng con này.
Truy vấn 2:phạm vi là [0, 2], mảng con ={4, 8, 1}. 1 hiện diện trong mảng con này.
Truy vấn 1:phạm vi là [4, 7], mảng con ={2, 9, 3, 5, 1}. 2 có trong mảng con này.
Phương pháp tiếp cận giải pháp
Một cách đơn giản để giải quyết vấn đề là duyệt qua mảng con và kiểm tra xem phần tử đã cho có nằm trong dải hay không.
Ví dụ
#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;
} Đầu ra
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
Đây là cách tiếp cận sử dụng một vòng lặp, do đó có độ phức tạp về thời gian theo thứ tự O (Q * N). Trong đó Q là số lượng truy vấn.
Một cách tiếp cận giải pháp tốt hơn có thể sử dụng một Cây phân đoạn để lưu trữ tất cả các chữ số có thể có (0 - 9). Để tránh các phần tử trùng lặp trong nút, chúng ta sẽ sử dụng cấu trúc dữ liệu tập hợp (nó có thuộc tính để loại bỏ các phần tử trùng lặp). Điều này sẽ giúp chúng tôi giảm tổng số phần tử trong mỗi nút xuống tối đa là 10.
Sau đó, đối với truy vấn, chúng tôi sẽ kiểm tra xem phần tử có hiện diện hay không trong phạm vi đã cho.
Ví dụ
#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;
} Đầu ra
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