查询以检查C ++中给定范围内是否存在给定数字

在这个问题中，我们给出了一个数组arr []和一些查询，每个查询由三个值L和R以及val组成。我们的任务是创建一个程序来解决查询，以检查C ++中给定范围内是否存在给定数字。

问题描述-

为了解决每个查询，我们需要检查给定元素val是否存在于L和R之间的给定范围内。

让我们举个例子来了解这个问题，

输入：arr [] = {4，8，1，7，2，9，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）。为了避免节点中出现重复元素，我们将使用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