정수를 포함하는 배열 arr[]이 제공됩니다. 목표는 각각의 고유한 요소 수가 원래 배열의 고유한 요소 수와 동일하도록 arr[]의 모든 하위 배열을 계산하는 것입니다. 원래 배열이 [1,1,2,3]이면 하위 배열은 [1,2,3] 및 [1,1,2,3]이 됩니다.
원래 배열의 총 고유 요소는 3입니다. 두 하위 배열의 총 고유 요소도 3입니다.
예를 들어 이해합시다.
입력 - arr[] ={1,2,1,2,3,4,2 };
출력 − 원본 배열과 동일한 총 고유 요소를 갖는 하위 배열의 개수는 − 6입니다.
설명 - arr[]의 고유한 요소는 4(1,2,3,4)입니다. 동일한 수의 고유 요소가 있는 하위 배열은 다음과 같습니다. ( 왼쪽에서 오른쪽으로 고유한 개수 )
[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2 ]
입력 - arr[] ={8,7,5,6,10};
출력 − 원본 배열과 동일한 총 고유 요소를 갖는 하위 배열의 개수는 − 1
설명 - arr[]의 고유한 요소는 5(5,6,7,8,10)입니다. 동일한 수의 고유한 요소가 있는 하위 배열은 다음과 같습니다. 1개만
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
정수의 배열 arr[]를 가져와 배열의 크기를 계산합니다.
-
함수 sub_ele_diff_one(int arr[], int size)는 배열을 취하고 1이 다른 연속 요소가 있는 하위 배열의 수를 반환합니다.
-
임시 변수 개수와 변수를 좌우로 가져옵니다.
-
임의의 쌍을 생성하기 위해 unordered_map 유형의 변수를 사용합니다.
-
0부터 배열 크기까지 FOR 루프를 시작하고 그 안에 unordered_map 내부에 arr[i] 값을 설정합니다.
-
이제 unordered_map의 크기를 계산하고 unordered_map을 지웁니다.
-
0부터 배열 크기까지 FOR 루프를 시작합니다.
-
루프 내에서 WHILE을 시작하여 오른쪽 <크기 및 왼쪽
까지 -
um[arr[right]]
값을 미리 증가시킵니다. -
이제 um[arr[right]] =1인지 확인한 다음 왼쪽 값을 1만큼 사전 증가시킵니다.
-
WHILE 외부에서 right 값을 1만큼 미리 증가시킵니다.
-
IF left =unordered_map의 크기를 확인한 다음 count를 count + size - right + 1로 설정합니다.
-
um[arr[i]]를 1만큼 감소
-
IF um[arr[i]] =0을 확인한 다음 왼쪽을 1만큼 감소
-
개수 반환
-
결과를 인쇄하십시오.
예시
#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size){
int count = 0, right = 0, left = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; ++i){
um[arr[i]] = 1;
}
int um_size = um.size();
um.clear();
for(int i = 0; i < size; ++i){
while (right < size && left < um_size){
++um[arr[right]];
if (um[arr[right]] == 1){
++left;
}
++right;
}
if (left == um_size){
count = count + (size - right + 1);
}
--um[arr[i]];
if (um[arr[i]] == 0){
--left;
}
}
return count;
}
int main(){
int arr[] = {4, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays having total distinct elements same as original array are: "<<sub_distinct(arr, size);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of subarrays having total distinct elements same as original array are: 1