Đếm các cặp chỉ số có các phần tử bằng nhau trong một mảng trong C ++

Chúng ta được cung cấp với một mảng N phần tử. Mục đích là tìm các cặp chỉ mục (i, j) có cùng giá trị phần tử sao cho i! =J. tức là Arr [i] =Arr [j] và i! =j. Điều này được sử dụng để làm cho các cặp găng tay có kích thước bằng nhau. Ngoài N găng tay, chỉ có găng tay có cặp là hữu ích để bán.

Chúng ta sẽ thực hiện điều này bằng cách chạy hai vòng lặp với 0 <=i 0 &&Arr [j]> 0 và i! =J. Nếu đúng, hãy tăng số lượng các cặp như vậy và đặt các phần tử này thành -1 (Arr [i] =Arr [j] =-1) để xóa chúng khỏi việc kiểm tra thêm vì không có găng tay nào có kích thước -1.

Hãy cùng hiểu với các ví dụ.

Đầu vào - Arr [] ={4,3,2,1,2,4} N =6

Đầu ra - Đếm các cặp chỉ số có các phần tử bằng nhau - 2

Giải thích -

count=0, Arr[]= [ 4,3,2,1,2,4 ]
Arr[0]=Arr[5], 0!=5, count=1 Arr[0]=Arr[5]=-1 → [ -1,3,2,1,2,-1 ]
Arr[2]=Arr[4], 2!=4, count=2 Arr[2]=Arr[4]=-1 → [ -1,3,-1,1,-1,-1 ]
Now array has no new pairs with equal values, i!=j and > -1. Total pairs=2

Đầu vào - Arr [] ={2,2,2,2,2} N =5

Đầu ra - Đếm các cặp chỉ số có các phần tử bằng nhau - 2

Giải thích -

count=0, Arr[]= [ 2,2,2,2,2 ]
Arr[0]=Arr[1], 0!=1, count=1 Arr[0]=Arr[1]=-1 → [ -1,-1,2,2,2 ]
Arr[2]=Arr[3], 2!=3, count=2 Arr[2]=Arr[3]=-1 → [ -1,-1,-1,-1,2 ]
Now array has no new pairs with equal values, i!=j and > -1. Total pairs=2

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

• Chúng tôi lấy một mảng số nguyên Arr [] được khởi tạo với các số ngẫu nhiên cho kích thước của găng tay> 0.

• Lấy một biến n lưu trữ độ dài của Arr [].

• Hàm countPairs (int arr [], int n) nhận một mảng, độ dài của nó làm đầu vào và trả về các cặp có kích thước bằng nhau và các chỉ mục khác nhau.

• Traverse mảng sử dụng hai vòng lặp for cho mỗi phần tử của cặp.

• Vòng ngoài từ 0 <=i

• Kiểm tra xem arr [i] và arr [j] có dương không. Nếu arr [i] ==arr [j] thì số gia tăng. (Tôi sẽ không bao giờ bằng j theo các điều kiện đặt trong vòng lặp, không cần phải so sánh).

• Bây giờ, hãy đặt arr [i] =arr [j] =- 1, để xóa chúng khỏi các so sánh sâu hơn.

• Ở cuối tất cả các vòng đếm sẽ có tổng số đôi găng tay.

• Trả lại kết quả là số lượng.

Ví dụ

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count equal elements to make pair of gloves
int countPairs(int arr[], int n){
   int count = 0;
   for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
         if(arr[i]==arr[j] && arr[i]>0 && arr[j]>0){
            count++;
            arr[i]=arr[j]=-1;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 1,2,4,2,1,2,4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout <<"Pair of gloves ( Equal element pairs ):"<<countPairs(arr, n);
   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 -

Pair of gloves ( Equal element pairs ):3.