Chúng ta được cung cấp một mảng các số nguyên dương. Mục đích là tìm số lượng các cặp phần tử của arr [] sao cho các cặp có phần tử (A, B) trong đó tần số của A là B lần và tần số của B là A.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - int arr [] ={3, 3, 3, 5, 5, 6, 6}
Đầu ra - Đếm các cặp trong một mảng sao cho tần số của một cặp ít nhất là giá trị của cặp khác là - 1
Giải thích - Các cặp hợp lệ trong mảng mà A xuất hiện B lần và B xuất hiện A lần là (3, 3) vì 3 xuất hiện 3 lần trong một mảng. Vì vậy, chỉ có một cặp hợp lệ do đó số lượng là 1.
Đầu vào - int arr [] ={3, 3, 3, 3, 3, 5, 5, 5, 6, 6}
Đầu ra - Đếm các cặp trong một mảng sao cho tần số của một cặp ít nhất là giá trị của cặp khác là - 1
Giải thích - Các cặp hợp lệ trong mảng mà A xuất hiện lần B và B xuất hiện lần A là (3, 3), (5, 5) và (3, 5) vì 3 xuất hiện 5 lần và 5 xuất hiện 3 lần trong một mảng . Vì vậy, có ba cặp hợp lệ do đó số lượng là 3.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận, trước tiên chúng ta sẽ tạo và điền một bản đồ không có thứ tự có chứa tần số của các phần tử của mảng. Duyệt qua bản đồ không có thứ tự bằng cách sử dụng vòng lặp for. Đối với mỗi phần tử và tần số của nó, nếu bất kỳ tần số nào được tìm thấy nhiều hơn, hãy đếm số cặp gia tăng.
-
Lấy một mảng arr [] các số nguyên.
-
Hàm frequency_other_value (int arr [], int size) lấy mảng và kích thước của nó và trả về số lượng các cặp sao cho các cặp là (A, B) trong đó A xuất hiện ít nhất B lần và ngược lại.
-
Lấy số lượng ban đầu là 0.
-
Lấy unrdered_map
-
Traverse map sử dụng for và cho mỗi giá trị đầu tiên của cặp start =it.second; (it =iterator), bản đồ đi ngang cho các tần số> =bắt đầu sử dụng vòng lặp for.
-
Số lượng tăng dần cho các cặp như vậy.
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầ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 pairs in an array such that frequency of one is at least value of other are: 1