이 문제에서는 n개의 정수 값으로 구성된 배열 arr[]이 제공됩니다. 그리고 Q는 각각 정수 k를 갖는 쿼리입니다. 우리의 임무는 Suffix에서 고유한 정수의 수에 대한 쿼리를 해결하는 프로그램을 만드는 것입니다.
문제 설명 − 접미사에서 고유한 정수에 대한 쿼리를 해결해야 합니다. 각 쿼리에 대해 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