Editorial for fanum: Số độc thân

Hiểu bài toán

Bài toán yêu cầu đếm số lượng các phần tử 'độc thân' (unique) trong một mảng. Một phần tử được coi là độc thân nếu nó xuất hiện đúng 1 lần trong toàn bộ mảng. Input gồm số lượng phần tử n và mảng a gồm n số nguyên dương. Output là số lượng số độc thân. Với ràng buộc n có thể lên tới 10^6 và giá trị phần tử lên tới 10^6, cần một giải pháp hiệu quả.

Các cách tiếp cận

Cách Brute Force (Đếm quảng)

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        bool is_unique = true;
        for (int j = 0; j < n; j++) {
            if (i != j && a[i] == a[j]) {
                is_unique = false;
                break;
            }
        }
        if (is_unique) {
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Giải pháp này sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài duyệt qua từng phần tử, vòng lặp trong kiểm tra xem phần tử đó có xuất hiện ở vị trí nào khác không. Nếu không có, ta tăng biến đếm.

• Ưu điểm: Dễ hiểu, không cần bộ nhớ phụ.
• Nhược điểm: Rất chậm, độ phức tạp O(n^2). Với n = 10^6, số phép toán khoảng 10^12, quá giới hạn thời gian cho phép. Chỉ phù hợp với dữ liệu nhỏ (n ≤ 1000).

Cách Sử dụng Mảng đếm (Frequency Array)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VAL 1000001

int main() {
    int n;
    scanf("%d", &n);
    int *a = (int*)malloc(n * sizeof(int));
    // Mảng đếm (frequency array) để lưu số lần xuất hiện của mỗi giá trị
    int *count = (int*)calloc(MAX_VAL, sizeof(int));

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        count[a[i]]++;
    }

    int unique_count = 0;
    // Duyệt lại mảng a để đếm các số có tần suất là 1
    for (int i = 0; i < n; i++) {
        if (count[a[i]] == 1) {
            unique_count++;
        }
    }

    printf("%d", unique_count);
    free(a);
    free(count);
    return 0;
}

• Time Complexity: O(n + M)
• Space Complexity: O(M)

Giải pháp tối ưu sử dụng kỹ thuật 'Frequency Array' (Mảng tần suất).

1. Tạo một mảng count kích thước đủ lớn (ví dụ 1000001) để lưu số lần xuất hiện của từng giá trị.
2. Duyệt mảng input một lần, cập nhật count[a[i]]++.
3. Duyệt mảng input một lần nữa (hoặc mảng count), nếu count[x] == 1 thì tăng biến đếm. Độ phức tạp thời gian là O(n) vì chỉ duyệt qua dữ liệu 2 lần. Độ phức tạp không gian là O(M) với M là giá trị tối đa của phần tử (10^6). Đây là cách làm hiệu quả nhất trong các điều kiện của bài toán.

Cách Sử dụng Hash Map (Bản đồ băm)

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 2000003 // Prime number > 10^6

typedef struct Node {
    int key;
    int count;
    struct Node *next;
} Node;

Node *hashTable[TABLE_SIZE] = {NULL};

int hash(int key) {
    return key % TABLE_SIZE;
}

void insert(int key) {
    int index = hash(key);
    Node *temp = hashTable[index];
    while (temp != NULL) {
        if (temp->key == key) {
            temp->count++;
            return;
        }
        temp = temp->next;
    }
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->count = 1;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

int getCount(int key) {
    int index = hash(key);
    Node *temp = hashTable[index];
    while (temp != NULL) {
        if (temp->key == key) {
            return temp->count;
        }
        temp = temp->next;
    }
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    int *a = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int unique_count = 0;
    for (int i = 0; i < n; i++) {
        if (getCount(a[i]) == 1) {
            unique_count++;
        }
    }

    printf("%d", unique_count);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Sử dụng Hash Map để lưu trữ tần suất.

1. Cấu trúc dữ liệu Node lưu key và count (dùng phương pháp xung đột nối链表).
2. Duyệt mảng, chèn vào Hash Map hoặc cập nhật count nếu đã tồn tại.
3. Kiểm tra lại mảng, với mỗi phần tử tra cứu trong Hash Map xem count có bằng 1 không. Giải pháp này có độ phức tạp O(n) về thời gian và O(n) về bộ nhớ. Nó linh hoạt hơn mảng đếm khi giá trị phần tử rất lớn (> 10^6), nhưng với ràng buộc của bài này thì mảng đếm đơn giản và nhanh hơn (tránh overhead của con trỏ và phân bổ bộ nhớ động).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vì giá trị a_i nhỏ (≤ 10^6), 'Frequency Array' (mảng đếm) là lựa chọn tối ưu nhất về độ phức tạp thời gian O(n) và cách cài đặt đơn giản.
• Phải đếm tần suất trước, sau đó mới kiểm tra điều kiện 'độc thân' (tần suất = 1).

Lỗi thường gặp

• Quên kiểm tra ràng buộc bộ nhớ khi khai báo mảng lớn (nên khai báo toàn cục hoặc dùng cấp phát động).
• Sử dụng giải thuật O(n^2)导致 TLE (Time Limit Exceeded) với n lớn.
• Lỗi logic: Đếm số lượng giá trị duy nhất (distinct values) thay vì số lượng số độc thân (unique elements). Ví dụ: [1, 2, 3] distinct là 3, unique là 3. [1, 1, 2] distinct là 2, unique là 1.