C++プログラムのサフィックスの個別の整数の数のクエリ

この問題では、n個の整数値の配列arr[]が与えられます。そして、Qはそれぞれ整数kを持つクエリを実行します。私たちのタスクは、サフィックス内の個別の整数の数のクエリを解決するプログラムを作成することです。

問題の説明 −接尾辞の個別の整数のクエリを解決する必要があります。クエリごとに、kからnまでの一意の要素の数を見つける必要があります。つまり、arr[k]からarr[n]までの一意の要素を数えます。

取得された配列は1つのインデックスが付けられています。

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

入力

arr[ ] = {5, 1, 2, 1, 6 , 5}, n = 6, Q = 3, query = {1, 3, 4}

出力

4 4 3

説明

For Query 1: k = 1, N = 6, Count of elements from arr[1] to arr[6]. Count = 4.
For Query 2: k = 3, N = 6, Count of elements from arr[3] to arr[6]. Count = 4
For Query 3: k = 4, N = 6, Count of elements from arr[4] to arr[6]. Count = 3

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

インデックスkからnまでを開始して、各クエリを解決するための問題の簡単な解決策。そして、配列のすべての一意の要素をカウントし、各クエリのカウントを返します。

効果的な解決策

この問題の効果的な解決策は、（n-1）から0までのインデックスの一意のカウントを格納する事前計算されたデータ構造を使用することです。これは、順序付けられていないセットを使用して重複要素の追加を排除することによって行われます。発生回数のために、補助配列を使用することもできます。

最後からk番目の要素まで配列の要素をデータ構造に追加し、データ構造内の要素の数を見つけます（k番目のインデックスの配列値の場合）。

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

例

#include <bits/stdc++.h>
using namespace std;
void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
   unordered_set<int> uniqueInts;
   int distIntCount[n + 1];
   for (int i = n - 1; i >= 0; i--) {
      uniqueInts.insert(arr[i]);
      distIntCount[i + 1] = uniqueInts.size();
   }
   for (int i = 0; i < Q; i++)
   cout<<"For Query "<<(i+1)<<": the number of distinct integers in Suffix is "<<distIntCount[queries[i]]<<endl;
}
int main() {
   int n = 6, Q = 3;
   int arr[n] = {5, 1, 2, 1, 6, 5};
   int queries[Q] = {1, 3, 4};
   solveQueries_DistInt(n, arr, Q, queries);
   return 0;
}

出力

For Query 1: the number of distinct integers in Suffix is 4
For Query 2: the number of distinct integers in Suffix is 4
For Query 3: the number of distinct integers in Suffix is 3