정수 요소를 포함하는 배열 arr[]이 제공됩니다. 목표는 각 하위 배열이 고유한 요소만 갖도록 arr[] 하위 배열의 요소에 의해 형성될 수 있는 쌍의 수를 찾는 것입니다. 배열이 [ 1,2,2,3,3 ]이면 고유한 요소만 있는 하위 배열은 [ 1,2 ] 및 [ 2,3 ]이 됩니다. 쌍은 (1,2) 및 (2,3)이므로 쌍의 개수는 2입니다.
예를 들어 이해하자
입력 - arr[] ={1,2,5,3 }
출력 − 고유한 요소 하위 배열로 형성된 쌍의 수는 − 6
입니다.설명 − 고유한 요소가 있는 하위 배열은 다음과 같습니다. [ 1,2,5, 3], 가능한 쌍 (1,2), (1,3), (1,5), (2,5), (2,3), (5,3)
총 6쌍입니다.
입력 - arr[] ={1,2,1,2,3}
출력 − 고유한 요소 하위 배열에 의해 형성된 쌍의 수는 − 5
입니다.설명 − 고유한 요소가 있는 하위 배열은 다음과 같습니다. -
[1,2] - pairs: (1,2) [2,1] - pairs: (2,1) [1,2,3] - pairs : (1,2), (2,3), (1,3) Total pairs : 5
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
정수 배열을 입력으로 사용합니다.
-
함수 distinct_pairs(int arr[], int size)는 배열을 가져와 고유한 요소 하위 배열로 구성된 Count 쌍을 반환합니다.
-
초기 카운트를 0으로 취합니다. 변수를 start=end=0으로 취합니다.
-
창의 요소를 표시하려면 벡터 검사(크기, 거짓)를 수행하십시오.
-
시작이 크기보다 작을 때까지 WHILE 루프 시작
-
루프 내에서 WHILE 다른 루프를 시작하여 크기보다 작게 시작하고 check[arr[star]] =0으로 설정한 다음 count를 start - end로 설정하고 check[arr[start]]를 true로 설정하고 시작을 1씩 증가시킵니다.
-
WHILE 루프를 시작보다 작은 끝까지 시작하고 시작이 크기와 같지 않고 check[arr[start]] =true로 설정한 다음 check[arr[end]] =false로 설정하고 끝도 1씩 증가시킵니다.
-
개수 반환
-
결과를 인쇄하십시오.
예시
#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
int count = 0;
int start = 0;
int end = 0;
vector<bool> check(size, false);
while (start < size){
while (start < size && !check[arr[start]]){
count += (start - end);
check[arr[start]] = true;
start++;
}
while (end < start && (start != size && check[arr[start]])){
check[arr[end]] = false;
end++;
}
}
return count;
}
int main(){
int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs formed by distinct element sub-arrays are: 17