Đếm các cặp duy nhất (arr [i], arr [j]) sao cho i <j trong C ++

Chúng ta được cung cấp một mảng chứa các phần tử nguyên. Mục tiêu là tìm các cặp phần tử duy nhất của mảng sao cho các cặp kiểu (arr [i], arr [j]) có chỉ mục sao cho i

Hãy cho chúng tôi hiểu với các ví dụ

Đầu vào - arr [] ={1,2,3};

Đầu ra - Đếm các cặp duy nhất (arr [i], arr [j]) sao cho i

Giải thích - Vì tất cả các yếu tố là duy nhất. Các cặp sẽ là -

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

Đầu vào - arr [] ={4,4,3,2};

Đầu ra - Đếm các cặp duy nhất (arr [i], arr [j]) sao cho i

Giải thích - Vì tất cả các yếu tố là duy nhất. Các cặp sẽ là -

(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

Cách tiếp cận được sử dụng trong chương trình dưới đây như sau

Chúng tôi sẽ sử dụng hai cách tiếp cận. Cách tiếp cận ngây thơ đầu tiên bằng cách sử dụng vòng lặp for. Bắt đầu duyệt qua mảng arr [] bằng cách sử dụng hai vòng lặp for. Từ i =0 đến i > se; Ở kích thước cuối của ‘se’ sẽ là số cặp duy nhất với i

Lấy mảng số nguyên arr [] với các phần tử nguyên và độ dài làm kích thước
Hàm unique_pair (int arr [], int size) nhận mảng và độ dài của nó và trả về số lượng các cặp duy nhất sao cho trong cặp (arr [i], arr [j]) index i
Lấy giá trị ban đầu của số đếm là 0.
Lấy một tập hợp ‘se’ chứa các cặp số nguyên. (đặt > se)
Bắt đầu duyệt qua arr [] bằng cách sử dụng hai vòng lặp for. từ i =0 đến i
Đối với mỗi cặp luôn là i
Ở cuối cả hai vòng lặp for, hãy cập nhật count =se.size ().
Đếm bây giờ có một số cặp trong ‘se’. (Tất cả đều là duy nhất).
Kết quả là số lượt trả lại.

Phương pháp tiếp cận hiệu quả

Trong cách tiếp cận này, chúng ta sẽ tìm thấy các phần tử duy nhất sau mỗi phần tử. arr [i] sẽ ghép nối với các phần tử khác biệt / duy nhất từ arr [i + 1 đến size-1]. Vì vậy, nếu có x phần tử duy nhất sau arr [i], thì arr [i] sẽ tạo thành cặp x. Vì vậy, trước tiên chúng ta sẽ tạo một mảng đánh dấu các phần tử duy nhất sau một chỉ mục i. Sau đó, thêm các số lượng riêng lẻ như vậy để có tổng số các cặp duy nhất.

Lấy mảng số nguyên arr [] với các phần tử nguyên và độ dài làm kích thước
Hàm unique_pair (int arr [], int size) nhận mảng và độ dài của nó và trả về số lượng các cặp duy nhất sao cho trong cặp (arr [i], arr [j]) index i
Lấy giá trị ban đầu của số đếm là 0.
Lấy biến tạm thời và đặt nó thành 0.
Lấy một mảng arr_2 [] có kích thước chiều dài và khởi tạo arr_2 [size-1] =0, vì phần tử cuối cùng có 0 phần tử duy nhất sau nó.
Tạo hai bộ số nguyên chọn và bỏ chọn.
Duyệt mảng từ phần tử cuối cùng sang phần tử đầu tiên.i =size-1 thành i> =0. Tìm kiếm arr [i] trong séc đã đặt.
Nếu không tìm thấy thì nó là duy nhất. Nhiệt độ tăng dần (tạm thời là số phần tử duy nhất sau arr [i]). Đặt arr_2 [i] =temp.
Else arr_2 [i] =tạm thời. Không tăng dần về nhiệt độ.
Chèn arr [i] để đặt séc. Bây giờ, lần xuất hiện tiếp theo của arr [i] sẽ không được xem xét.
Sau khi kết thúc vòng lặp for này. arr_2 [] đã được cập nhật.
Bây giờ đi ngang arr [] từ chỉ mục i =0 đến i
Thêm arr [i] để bỏ chọn. Bây giờ lần xuất hiện tiếp theo của arr [i] sẽ không được xem xét.
Ở cuối số đếm có các cặp duy nhất sao cho i
Kết quả là số lượt trả lại.

Ví dụ (cách tiếp cận ngây thơ)

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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

Ví dụ (cách tiếp cận hiệu quả)

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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