Đếm cặp trong mảng sao cho tần suất một phần tử bằng giá trị phần tử kia trong C++

Cho mảng số nguyên dương. Tìm số cặp (A, B) sao cho tần suất của A ≥ B và tần suất của B ≥ A.

Ví dụ

Đầu vào − arr[] = {3, 3, 3, 5, 5, 6, 6}

Đầu ra − 1

Giải thích − Cặp (3,3) vì 3 xuất hiện 3 lần.

Đầu vào − arr[] = {3, 3, 3, 3, 3, 5, 5, 5, 6, 6}

Đầu ra − 3

Giải thích − Các cặp: (3,3), (5,5), (3,5).

Phương pháp giải

Tạo unordered_map tần suất. Duyệt map, với mỗi phần tử start = key, end = freq. Duyệt j từ 1 đến end, nếu freq[j] >= start thì count++.

• Hàm frequency_other_value(int arr[], int len).
• Khởi tạo count = 0, unordered_map um.
• Điền tần suất vào um.
• Duyệt um: start = it.first, end = it.second.
• Với j = 1..end: nếu um[j] >= start thì count++.
• Trả về count.

Ví dụ code

#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

Count of pairs in an array such that frequency of one is at least value of other are: 1