양의 정수 배열이 제공됩니다. 목표는 A의 빈도가 B 배이고 B의 빈도가 A인 쌍에 요소( A, B )가 있도록 arr[] 요소의 쌍 수를 찾는 것입니다.
예를 들어 이해합시다.
입력 - 정수 arr[] ={ 3, 3, 3, 5, 5, 6, 6}
출력 − 하나의 빈도가 다른 하나의 값 이상인 배열의 쌍 수는 − 1
설명 - 배열에서 A가 B번 발생하고 B가 A번 발생하는 배열의 유효한 쌍은 (3, 3)입니다. 3은 배열에서 3번 발생하기 때문입니다. 따라서 유효한 쌍은 하나만 있으므로 개수는 1입니다.
입력 - 정수 arr[] ={ 3, 3, 3, 3, 3, 5, 5, 5, 6, 6}
출력 − 하나의 빈도가 다른 하나의 값 이상인 배열의 쌍 수는 − 1
설명 - 배열에서 A가 B번 발생하고 B가 A번 발생하는 배열의 유효한 쌍은 배열에서 3이 5번 발생하고 5가 3번 발생하므로 (3, 3), (5, 5) 및 (3, 5)입니다. . 따라서 세 개의 유효한 쌍이 있으므로 개수는 3입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
접근 방식에서 우리는 먼저 배열 요소의 빈도를 포함하는 정렬되지 않은 맵을 만들고 채웁니다. for 루프를 사용하여 unordered_map을 탐색합니다. 각 요소 및 해당 빈도에 대해 빈도가 더 많이 발견되면 쌍의 수를 증가시킵니다.
-
정수 배열 arr[]을 가져옵니다.
-
함수 frequency_other_value(int arr[], int size)는 배열과 배열의 크기를 사용하여 쌍이 (A,B)가 되도록 쌍의 개수를 반환합니다. 여기서 A는 최소 B번 발생하고 그 반대도 마찬가지입니다.
-
초기 카운트를 0으로 합니다.
-
arr[]의 요소와 해당 빈도에 대해 unordered_map
-
for 및 쌍 start=it.second의 첫 번째 값 각각에 대해 사용하는 트래버스 맵; (it=iterator), 주파수에 대한 트래버스 맵>=for 루프 사용 시작
-
이러한 쌍에 대한 증분 수.
-
결과로 카운트를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int frequency_other_value(int arr[], int len){
int count = 0;
unordered_map<int, int> um;
for (int i = 0; i < len; ++i){
um[arr[i]]++;
}
for (auto it : um){
int start = it.first;
int end = it.second;
for (int j = 1; j <= end; j++){
if (um[j] >= start){
count++;
}
}
}
return count;
}
int main(){
int arr[] = { 3, 3, 3, 5, 5, 6, 6};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs in an array such that frequency of one is at least value of other are: "<<frequency_other_value(arr, size);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs in an array such that frequency of one is at least value of other are: 1