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ử (p, q) trong đó p xuất hiện trong mảng ít nhất q lần và q xuất hiện trong mảng ít nhất p lần.
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ột mảng mà p xảy ra q lần và q xảy ra p lần là (3, 3) vì 3 là 3 xuất hiệ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ột mảng mà p xảy ra q lần và q xảy ra p lần là (3, 3), (5, 5) và (3, 5) là 3 xảy ra 5 lần và 5 xảy ra 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
-
Nhập một mảng các phần tử số nguyên và tính toán kích thước của một mảng và chuyển dữ liệu vào hàm để xử lý thêm
-
Khai báo số lượng biến tạm thời để lưu trữ các lần xuất hiện của p và q
-
Tạo một vec biến của loại vectơ và ô của loại không có thứ tự_map
-
Bắt đầu vòng lặp FOR từ 0 cho đến hết kích thước của một mảng
-
Bên trong vòng lặp, đặt um [arr [i]] bằng 1 và kiểm tra NẾU ô là 1 rồi nhấn arr [i] trong vectơ
-
Bắt đầu một vòng lặp FOR khác từ 0 cho đến khi có kích thước bằng vectơ và kiểm tra IF um [vec [i]
-
Bên trong vòng lặp j kiểm tra IF um [j]> =vec [i] sau đó tăng số lượng lên 1
-
Trả lại số lượng
-
In kết quả.
Ví dụ
#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;
} Đầ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 (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1