C++のサブ配列内の個別の要素の数のクエリ

この問題では、サイズnの配列arr[]が与えられます。そして、それぞれが2つの要素lとrで構成されるQクエリ。私たちのタスクは、C++のサブ配列内の多数の個別の要素のクエリを解決するプログラムを作成することです。

問題の説明 −ここでは、各クエリについて、arr[l]からarr[r]までのサブ配列内の個別の整数の総数を見つける必要があります。

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

入力

arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}}

出力

3
4

説明

クエリ1：l=1およびr=4の場合、subarray [1 ... 4] ={6、1、6、5}、個別の要素は=3です。

クエリ2− l=0およびr=6の場合、subarray [0 ... 6] ={5、6、1、6、5、2、1}、個別の要素は=4です。

ソリューションアプローチ

この問題を解決するために、セットデータ構造を使用します。その長さは、クエリで指定された範囲の配列の個別の要素の数を示します。クエリごとに、配列内の範囲のすべての要素をセットに挿入します。サブアレイの重複する要素はすべて破棄され、個別の要素のみが保存されるため、セットのサイズによって個別の要素の数がわかります。

ソリューションの動作を説明するプログラム

例

#include<bits/stdc++.h>
using namespace std;

int solveQuery(int arr[], int l, int r) {

   set<int> distElements;
   for (int i = (r); i >= (l); i--)
   distElements.insert(arr[i]);
   return distElements.size();
}

int main() {

   int arr[] = {5, 6, 1, 6, 5, 2, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   int Q = 2;
   int query[Q][2] = {{1, 4}, {0,6}};
   for(int i = 0; i < Q; i++)
   cout<<"For Query "<<(i+1)<<": The number of distinct elements in subarray is "<<solveQuery(arr,    query[i][0], query[i][1])<<"\n";
   return 0;
}

出力

For Query 1: The number of distinct elements in subarray is 3
For Query 2: The number of distinct elements in subarray is 4