양의 정수 배열이 제공됩니다. 목표는 쌍에 요소( p, q )가 포함되도록 arr[] 요소 쌍의 개수를 찾는 것입니다. 여기서 p는 배열에서 최소 q번 발생하고 q는 배열에서 최소 p번 발생합니다.
예를 들어 이해합시다.
입력 - 정수 arr[] ={ 3, 3, 3, 5, 5, 6, 6}
출력 − 하나의 빈도가 다른 하나의 값 이상인 배열의 쌍 수는 − 1
설명 - 배열에서 p가 q번 발생하고 q가 p번 발생하는 배열의 유효한 쌍은 (3, 3)입니다. 3은 배열에서 3번 발생하기 때문입니다. 따라서 유효한 쌍은 하나만 있으므로 개수는 1입니다.
입력 - 정수 arr[] ={ 3, 3, 3, 3, 3, 5, 5, 5, 6, 6}
출력 − 하나의 빈도가 다른 하나의 값 이상인 배열의 쌍 수는 − 1
설명 - 배열에서 p가 q번 발생하고 q가 p번 발생하는 배열에서 유효한 쌍은 배열에서 3이 5번 발생하고 5가 3번 발생하므로 (3, 3), (5, 5) 및 (3, 5)입니다. . 따라서 세 개의 유효한 쌍이 있으므로 개수는 3입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 요소의 배열을 입력하고 배열의 크기를 계산하고 추가 처리를 위해 데이터를 함수에 전달합니다.
-
p 및 q의 발생을 저장할 임시 변수 개수 선언
-
vector 유형의 변수 vec와 unordered_map 유형의 um 생성
-
0부터 배열 크기까지 FOR 루프 시작
-
루프 내에서 um[arr[i]]를 1로 설정하고 um이 1인지 확인한 다음 벡터에서 arr[i]를 푸시합니다.
-
0에서 벡터 크기까지 다른 루프 FOR를 시작하고 IF um[vec[i]
-
루프 내에서 j IF um[j]>=vec[i]를 확인한 다음 카운트를 1 증가시킵니다.
-
개수 반환
-
결과를 인쇄하십시오.
예
#include <bits/stdc++.h>
using namespace std;
int pair_count(int arr[], int len){
int count = 0;
vector<int> vec;
unordered_map<int, int> um;
for (int i = 0; i < len; i++){
um[arr[i]]++;
if (um[arr[i]] == 1){
vec.push_back(arr[i]);
}
}
for (int i = 0; i < vec.size(); i++){
if (um[vec[i]] < vec[i]){
continue;
}
else if (um[vec[i]] == vec[i]){
count++;;
}
else{
count++;
for (int j = vec[i] + 1; j <= um[vec[i]]; j++){
if (um[j] >= vec[i]){
count++;
}
}
}
}
return count;
}
int main(){
int arr[] = { 1, 1, 1, 5, 5, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least
p times are: "<<pair_count(arr, size);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1