정수 요소를 포함하는 배열이 제공됩니다. 목표는 유형 쌍(arr[i],arr[j])이 i

예를 들어 이해하자

입력 - arr[] ={1,2,3};

출력 − i 인 고유 쌍의 개수(arr[i], arr[j])

설명 − 모든 요소가 고유하므로. 쌍은 -

(1,2) - ( arr[0],arr[1] ) 0<1
(1,3) - ( arr[0], arr[2] ) 0<2
(2,3) - ( arr[1],arr[2] ) 1<2

입력 - arr[] ={ 4,4,3,2};

출력 − i 인 고유 쌍(arr[i], arr[j])의 개수

설명 − 모든 요소가 고유하므로. 쌍은 -

(4,4) - ( arr[0],arr[1] ) 0<1
(4,3) - ( arr[0], arr[2] ) 0<2
(4,2) - ( arr[0],arr[3] ) 0<3
(3,2) - ( arr[2],arr[3] ) 2<3

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

우리는 두 가지 접근 방식을 사용할 것입니다. for 루프를 사용하는 최초의 순진한 접근 방식. 두 개의 for 루프를 사용하여 배열 arr[] 순회를 시작합니다. i=0에서 i<길이-1까지 및 j=i+1에서 j<길이까지. 이런 식으로 항상 i> se에 쌍(arr[i],arr[j])을 추가합니다. 'se'의 끝 크기에서 i가 있는 고유 쌍의 수가 됩니다.

• 정수 요소와 길이를 크기로 사용하여 정수 배열 arr[] 사용

• 함수 unique_pair(int arr[], int size)는 배열과 그 길이를 취하고 쌍(arr[i],arr[j])에서 인덱스 i가 되도록 고유한 쌍의 수를 반환합니다.

• count의 초기값을 0으로 합니다.

• 정수 쌍을 포함하는 집합 'se'를 취합니다. (set> se)

• 두 개의 for 루프를 사용하여 arr[] 순회를 시작합니다. i=0에서 i까지

• 항상 i를 사용하여 'se'에 쌍(arr[i],arr[j])을 추가합니다.

• 두 for 루프의 끝에서 count=se.size()를 업데이트합니다.

• 이제 Count에는 'se'에 여러 쌍이 있습니다. ( 모두 고유합니다 ).

• 결과로 카운트를 반환합니다.

효율적인 접근

이 접근 방식에서는 각 요소 다음에 고유한 요소를 찾습니다. arr[i]는 arr[ i+1 ~ size-1 ]의 고유한 요소와 쌍을 이룹니다. 따라서 arr[i] 뒤에 x개의 고유한 요소가 있으면 arr[i]는 x개의 쌍을 만듭니다. 따라서 먼저 인덱스 i 다음에 고유한 요소를 표시하는 배열을 만듭니다. 그런 다음 총 고유 쌍에 대해 이러한 개별 수를 추가합니다.

• 정수 요소와 길이를 크기로 사용하여 정수 배열 arr[] 사용

• 함수 unique_pair(int arr[], int size)는 배열과 그 길이를 취하고 쌍(arr[i],arr[j])에서 인덱스 i가 되도록 고유한 쌍의 수를 반환합니다.

• count의 초기값을 0으로 합니다.

• 임시 변수를 가져 와서 0으로 설정하십시오.

• 마지막 요소 뒤에 0개의 고유 요소가 있으므로 길이 크기의 배열 arr_2[]를 가져오고 arr_2[size-1]=0을 초기화합니다.

• 두 개의 정수 집합을 선택하고 선택을 취소합니다.

• 마지막 요소에서 first.i=size-1에서 i>=0으로 배열을 순회합니다. 세트 체크에서 arr[i]를 검색하세요.

• 발견되지 않으면 고유합니다. temp를 증가시킵니다(temp는 arr[i] 뒤의 고유 요소 수입니다). 설정 arr_2[i]=temp.

• 그렇지 않으면 rr_2[i]=temp. 온도 증가 없이.

• arr[i]를 삽입하여 확인을 설정합니다. 이제 다음 ar[i] 발생은 고려되지 않습니다.

• 이 for 루프가 끝난 후. rr_2[]가 업데이트되었습니다.

• 이제 인덱스 i=0에서 i

• arr[i]를 추가하여 선택 취소를 설정합니다. 이제 다음 ar[i] 발생은 고려되지 않습니다.

• 마지막 개수에는 고유 쌍(arr[i],arr[j])에 대해 i

• 결과로 카운트를 반환합니다.

예(순진한 접근 방식)

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
   int count = 0;
   set<pair<int, int>> se;
   for(int i = 0; i < (size - 1); i++){
      for (int j = i + 1; j < size; j++){
         se.insert(make_pair(arr[i], arr[j]));
      }
   }
   count = se.size();
   return count;
}
int main(){
   int arr[] = { 4, 3, 1, 6, 7 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Count of unique pairs (arr[i], arr[j]) such that i & j are: 10

예(효율적인 접근)

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
   int count = 0, temp = 0;
   int arr_2[size];
   arr_2[size-1] = 0;
   set<int> check, uncheck;
   for (int i = size - 1; i > 0; i--){
      auto set = check.find(arr[i]);
      if (set != check.end()){
         arr_2[i - 1] = temp;
      }
      else{
         arr_2[i - 1] = ++temp;
      }
      check.insert(arr[i]);
   }
   for (int i = 0; i < size - 1; i++){
      auto set = uncheck.find(arr[i]);
      if (set != uncheck.end()){
         continue;
      }
      count += arr_2[i];
      uncheck.insert(arr[i]);
   }
   return count;
}
int main(){
   int arr[] = { 4, 3, 1, 6, 7 };
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10