特定の数字がC++の特定の範囲に存在するかどうかを確認するためのクエリ

この問題では、配列arr []と、それぞれが3つの値LとR、およびvalで構成されるいくつかのクエリを指定しました。私たちのタスクは、クエリを解決して、C++の特定の範囲に特定の数字が存在するかどうかを確認するプログラムを作成することです。

問題の説明-

各クエリを解決するには、指定された要素valがLとRの間の指定された範囲に存在するかどうかを確認する必要があります。

問題を理解するために例を見てみましょう

入力 ：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