Đếm phần tử khác nhau trong mảng C++

Cho một mảng không sắp xếp chứa các phần tử lặp lại, nhiệm vụ là đếm số phần tử khác nhau (distinct elements) trong mảng.

Ví dụ

Input - arr[] = {1, 1, 2, 3, 3, 4, 4} Output - count is 4

Giải thích - 4 phần tử khác nhau: 1, 2, 3, 4.

Input - arr[] = {1, 2, 3, 4, 5, 5, 5, 5} Output - count is 5

Phương pháp 1: Sắp xếp (Sorting)

• Sắp xếp mảng bằng sort()
• Duyệt mảng, bỏ qua các phần tử trùng lặp liền kề
• Độ phức tạp: O(n log n)

Phương pháp 2: Không sắp xếp (Brute Force)

• Với mỗi phần tử, kiểm tra xem nó có xuất hiện trước đó không
• Nếu chưa xuất hiện, tăng count
• Độ phức tạp: O(n²)

Ví dụ code C++ - Có sắp xếp

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

int distinct_elements(int arr[], int n) {
    sort(arr, arr + n);
    int count = 0;
    for (int i = 0; i < n; i++) {
        while (i < n - 1 && arr[i] == arr[i + 1])
            i++;
        count++;
    }
    return count;
}

int main() {
    int arr[] = {3, 6, 5, 8, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "count is " << distinct_elements(arr, n);
    return 0;
}

Ví dụ code C++ - Không sắp xếp

#include <iostream>
using namespace std;

int countDistinct(int a[], int size) {
    int count = 1;
    for (int i = 1; i < size; i++) {
        int j;
        for (j = 0; j < i; j++) {
            if (a[i] == a[j]) break;
        }
        if (i == j) count++;
    }
    return count;
}

int main() {
    int a[] = {3, 6, 5, 8, 2, 3, 4};
    int size = sizeof(a) / sizeof(a[0]);
    cout << "count is " << countDistinct(a, size);
    return 0;
}

Kết quả

count is 6