이 문제에서는 배열 arr[]와 각각 L과 R, val의 세 값으로 구성된 일부 쿼리를 제공했습니다. 우리의 임무는 C++에서 주어진 범위에 주어진 숫자가 존재하는지 확인하기 위해 쿼리를 푸는 프로그램을 만드는 것입니다.
문제 설명-
각 쿼리를 풀기 위해서는 주어진 요소 val이 L과 R 사이의 주어진 Range에 존재하는지 확인해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 :arr[] ={4, 8, 1, 7, 2, 9, 3, 5, 1}
Q =3
쿼리 ={{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)를 저장하기 위해 세그먼트 트리를 사용할 수 있습니다. 노드에서 중복 요소를 피하기 위해 우리는 세트 데이터 구조를 사용할 것입니다(중복 요소를 제거하는 속성이 있음). 이렇게 하면 각 노드의 총 요소 수를 최대 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