이 문제에서는 크기가 n인 배열 arr[]이 제공됩니다. 그리고 Q 쿼리는 각각 두 개의 요소 l과 r로 구성됩니다. 우리의 임무는 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