Đếm tần suất phần tử mảng trong C++

Cho mảng số nguyên có thể trùng lặp. Đếm tần suất của từng giá trị khác nhau.

Ví dụ: {1,1,2,3,4,1,2,3} → 1:3, 2:2, 3:2, 4:1.

Hai cách:

• Cách 1 (O(n^2)): Mảng boolean check đánh dấu đã đếm, vòng lặp lồng.
• Cách 2 (O(n)): Dùng unordered_map đếm tần suất, sau đó duyệt map in ra.

Ví dụ (Cách 1)

#include <bits/stdc++.h>
using namespace std;

void frequency(int arr[], int size) {
    vector<bool> check(size, false);
    for (int i = 0; i < size; i++) {
        if (check[i]) continue;
        int count = 1;
        for (int j = i+1; j < size; j++)
            if (arr[i] == arr[j]) {
                check[j] = true;
                count++;
            }
        cout << "frequency of " << arr[i] << " is: " << count << endl;
    }
}

int main() {
    int arr[] = {1,2,3,1,2,3};
    int size = sizeof(arr) / sizeof(arr[0]);
    frequency(arr, size);
    return 0;
}

Ví dụ (Cách 2 - unordered_map)

#include <bits/stdc++.h>
using namespace std;

void frequency(int arr[], int size) {
    unordered_map<int, int> um;
    for (int i = 0; i < size; i++)
        um[arr[i]]++;
    for (auto x : um)
        cout << "frequency of " << x.first << " is: " << x.second << endl;
}

int main() {
    int arr[] = {1,2,3,1,2,3};
    int size = sizeof(arr) / sizeof(arr[0]);
    frequency(arr, size);
    return 0;
}

Đầu ra

frequency of 1 is: 2
frequency of 2 is: 2
frequency of 3 is: 2