Hiểu bài toán

Bài toán yêu cầu xác định xem một giá trị x có tồn tại trong một mảng gồm n số nguyên hay không. Nếu x xuất hiện ít nhất một lần, in ra 'YES', ngược lại in ra 'NO'. Dữ liệu đầu vào gồm số phần tử n (đến $10^6$), giá trị cần tìm x, và n phần tử của mảng. Các giá trị có thể âm và nằm trong khoảng đến $10^9$.

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

Cách Duyệt tuần tự (Brute Force)

#include <stdio.h>

int main(){
    int n;
    scanf("%d", &n);
    int x;
    scanf("%d", &x);
    int a[10000];
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    for(int i=0;i<n;i++){
        if(a[i]==x){
            printf("YES");
            return 0;
        }
    }
    printf("NO");
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Chúng ta đọc toàn bộ mảng vào bộ nhớ, sau đó sử dụng một vòng lặp để duyệt qua từng phần tử. Nếu tìm thấy phần tử có giá trị bằng x, ta in ra 'YES' và kết thúc chương trình ngay lập tức. Nếu vòng lặp kết thúc mà không tìm thấy, ta in ra 'NO'.

Cách Tối ưu hóa nhập xuất (Tìm kiếm trong luồng)

#include <stdio.h>
int main()
{
    int n, x;
    scanf("%d%d", &n, &x);
    int a[n];
    int oke = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] == x)
        {
            oke = 1;
        }
    }
    if (oke)
    {
        printf("YES");
    }
    else
    {
        printf("NO");
    }
}

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

Cách tiếp cận này tương tự về logic nhưng tối ưu hơn về thời gian thực thi. Thay vì nhập toàn bộ mảng xong mới bắt đầu tìm kiếm, ta kết hợp việc nhập và kiểm tra trong cùng một vòng lặp. Khi nhập một phần tử, ta so sánh ngay với x. Nếu khớp, ta bật cờ hiệu oke. Mặc dù vẫn cần lưu mảng (để đọc đúng thứ tự nếu cần, dù trong code này không bắt buộc phải lưu toàn bộ nếu chỉ cần tìm kiếm), việc kiểm tra sớm có thể giúp ta nhận biết kết quả nhanh hơn về mặt logic (dù độ phức tạp vẫn là O(n)).

Cách Đếm số lần xuất hiện (Counting)

#include <stdio.h>

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

int find_x (int a[], int n, int x) {
    int count = 0;
    for (int i=0; i<n; i++) {
        if (a[i]==x) {
            count ++;
        }
    }
    return count;

}

int main () {
    int n, a[100],x;
    scanf ("%d %d", &n, &x);
    if (n<=0) {
        printf("Invalid input\n");
        return 0;
    }
    nhap(a,n);
    int find = find_x (a,n,x);
    if (find >=1) {
        printf ("YES");
    }
    else {
        printf ("NO");
    }

    return 0;
}

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

Phương pháp này đếm chính xác số lần x xuất hiện trong mảng. Hàm find_x duyệt qua mảng và tăng biến đếm mỗi khiเจอ giá trị cần tìm. Cuối cùng, ta chỉ cần kiểm tra xem biến đếm có lớn hơn hoặc bằng 1 hay không. Về độ phức tạp, phương pháp này không khác biệt nhiều so với hai cách trên, nhưng nó cung cấp thêm thông tin về số lượng (nếu cần).

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

Bài học kinh nghiệm

• Bài toán này thuộc nhóm tìm kiếm (Search). Với ràng buộc $n \le 10^6$, giải thuật duyệt mảng O(n) là hoàn toàn đủ nhanh (thường chạy trong < 1 giây).
• Trong C/C++, có thể tối ưu hóa tốc độ nhập xuất bằng scanf/printf thay vì cin/cout nếu xử lý dữ liệu lớn, và nên sử dụng mảng động hoặc mảng tĩnh lớn.
• Nếu mảng đã được sắp xếp sẵn, ta có thể dùng Binary Search để giảm thời gian xuống O(log n). Tuy nhiên, với mảng đầu vào chưa được sắp xếp, giải pháp duy nhất là duyệt toàn bộ (O(n)).

Lỗi thường gặp

• Lỗi khai báo mảng: int a[n] trong C yêu cầu trình biên dịch hỗ trợ biến thể (C99 trở lên). Nếu n quá lớn, việc khai báo mảng tĩnh trên stack có thể gây tràn bộ nhớ stack (Stack Overflow). Nên dùng cấp phát động (malloc) hoặc mảng toàn cục.
• Quên kiểm tra điều kiện biên hoặc nhập sai định dạng dữ liệu.
• Sử dụng cin/cout cho dữ liệu lớn có thể gây chậm so với scanf/printf.