Đếm phần tử chỉ có trong mảng đầu tiên không có trong mảng thứ hai C++

Cho hai mảng arr_1[] và arr_2[], nhiệm vụ là đếm số phần tử xuất hiện trong arr_1[] nhưng không xuất hiện trong arr_2[] (xét cả tần suất).

Ví dụ

Input - arr_1[] = {1, 2, 3, 4}, arr_2[] = {1, 5, 6, 7, 8} Output - count is 3

Giải thích - Phần tử 1 xuất hiện ở cả hai mảng, nên chỉ đếm 2,3,4.

Input - arr_1[] = {10, 20, 30, 40, 50}, arr_2[] = {10, 20, 30, 60} Output - count is 2

Phương pháp tiếp cận

• Dùng unordered_map lưu tần suất các phần tử trong arr_1[]
• Duyệt arr_2[], giảm tần suất trong map nếu phần tử tồn tại
• Duyệt lại arr_1[], đếm các phần tử còn tần suất > 0 (đặt về 0 sau khi đếm để tránh trùng)

Ví dụ code C++

#include <iostream>
#include <unordered_map>
using namespace std;

int elements_count(int arr_1[], int arr_2[], int m, int n) {
    unordered_map<int, int> up;
    for (int i = 0; i < m; i++)
        up[arr_1[i]]++;

    for (int i = 0; i < n; i++) {
        if (up.find(arr_2[i]) != up.end() && up[arr_2[i]] != 0)
            up[arr_2[i]]--;
    }

    int result = 0;
    for (int i = 0; i < m; i++) {
        if (up[arr_1[i]] != 0) {
            result++;
            up[arr_1[i]] = 0;
        }
    }
    return result;
}

int main() {
    int arr_1[] = {2, 4, 4, 6, 6, 6, 8, 9};
    int arr_2[] = {2, 2, 4, 6, 6};
    int m = sizeof(arr_1) / sizeof(arr_1[0]);
    int n = sizeof(arr_2) / sizeof(arr_2[0]);
    cout << "count is " << elements_count(arr_1, arr_2, m, n);
    return 0;
}

Kết quả

count is 4